5 1 2 2 4 2 5 1 3 1 2 3 4 5 6 4 2 3 2 1 2 4 2 3 1 3 5 3 2 1 4 4 1 4
3 -1 7HintWe define the illegal situation of different operations: In first operation: if node x and y belong to a same tree, we think it‘s illegal. In second operation: if x = y or x and y not belong to a same tree, we think it‘s illegal. In third operation: if x and y not belong to a same tree, we think it‘s illegal. In fourth operation: if x and y not belong to a same tree, we think it‘s illegal.
#include<stdio.h>
#include<string.h>
#include<queue>
#include<iostream>
#define INF 0x7fffffff
#define N 300030
#define max(a,b) (a>b?a:b)
using namespace std;
int vis[N];
struct LCT
{
int bef[N],pre[N],next[N][2],key[N],add[N];
int rev[N],maxn[N];
void init()
{
memset(pre,0,sizeof(pre));
memset(next,0,sizeof(next));
rev[0]=rev[1]=0;
add[0]=add[1]=0;
bef[0]=bef[1]=0;
maxn[0]=key[0]=0;
}
void update_add(int x,int val)
{
if(x)
{
add[x]+=val;
key[x]+=val;
maxn[x]+=val;
}
}
void update_rev(int x)
{
if(!x)
return;
swap(next[x][0],next[x][1]);
rev[x]^=1;
}
void pushup(int x)
{
maxn[x] = max(key[x], max(maxn[next[x][0]], maxn[next[x][1]]));
}
void pushdown(int x)
{
if(add[x])
{
update_add(next[x][0],add[x]);
update_add(next[x][1],add[x]);
add[x]=0;
}
if(rev[x])
{
update_rev(next[x][0]);
update_rev(next[x][1]);
// swap(next[x][0],next[x][1]);
rev[x]=0;
}
}
void rotate(int x,int kind)
{
int y,z;
y=pre[x];
z=pre[y];
pushdown(y);
pushdown(x);
next[y][!kind]=next[x][kind];
pre[next[x][kind]]=y;
next[z][next[z][1]==y]=x;
pre[x]=z;
next[x][kind]=y;
pre[y]=x;
pushup(y);
}
void splay(int x)
{
int rt;
for(rt=x;pre[rt];rt=pre[rt]);
if(x!=rt)
{
bef[x]=bef[rt];
bef[rt]=0;
pushdown(x);
while(pre[x])
{
if(next[pre[x]][0]==x)
{
rotate(x,1);
}
else
rotate(x,0);
}
pushup(x);
}
}
void access(int x)
{
int fa;
for(fa=0;x;x=bef[x])
{
splay(x);
pushdown(x);
pre[next[x][1]]=0;
bef[next[x][1]]=x;
next[x][1]=fa;
pre[fa]=x;
bef[fa]=0;
fa=x;
pushup(x);
}
}
int getroot(int x)
{
access(x);
splay(x);
while(next[x][0])
x=next[x][0];
return x;
}
void makeroot(int x)
{
access(x);
splay(x);
update_rev(x);
}
void link(int x,int y)
{
makeroot(x);
makeroot(y);
bef[x]=y;
}
void cut(int y,int x)
{
makeroot(y);
access(x);
splay(x);
bef[next[x][0]]=bef[x];
bef[x]=0;
pre[next[x][0]]=0;
next[x][0]=0;
pushup(x);
}
void change(int x,int y,int val)
{
access(y);
for(y=0;x;x=bef[x])
{
splay(x);
if(!bef[x])
{
key[x]+=val;
update_add(y,val);
update_add(next[x][1],val);
return;
}
pushdown(x);
pre[next[x][1]]=0;
bef[next[x][1]]=x;
next[x][1]=y;
pre[y]=x;
bef[y]=0;
y=x;
pushup(x);
}
}
int query(int x,int y)
{
access(y);
for(y=0;x;x=bef[x])
{
splay(x);
if(!bef[x])
{
return max(key[x],max(maxn[next[x][1]],maxn[y]));
}
pushdown(x);
pre[next[x][1]]=0;
bef[next[x][1]]=x;
next[x][1]=y;
pre[y]=x;
bef[y]=0;
y=x;
pushup(x);
}
}
}lct;
struct s
{
int u,v,next;
}edge[N<<1];
int head[N],cnt;
void add(int u,int v)
{
edge[cnt].u=u;
edge[cnt].v=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
void bfs(int u)
{
queue<int>q;
memset(vis,0,sizeof(vis));
vis[u]=1;
q.push(u);
while(!q.empty())
{
u=q.front();
q.pop();
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(!vis[v])
{
lct.bef[v]=u;
vis[v]=1;
q.push(v);
}
}
}
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int i;
cnt=0;
memset(head,-1,sizeof(head));
for(i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
lct.init();
for(i=1;i<=n;i++)
{
scanf("%d",&lct.key[i]);
}
bfs(1);
int q;
scanf("%d",&q);
while(q--)
{
int op,x,y;
scanf("%d%d%d",&op,&x,&y);
if(op==1)
{
if(lct.getroot(x)==lct.getroot(y))
{
printf("-1\n");
}
else
lct.link(x,y);
}
else
if(op==2)
{
if(x==y||lct.getroot(x)!=lct.getroot(y))
{
printf("-1\n");
}
else
lct.cut(x,y);
}
else
if(op==3)
{
int z;
scanf("%d",&z);
if(lct.getroot(y)!=lct.getroot(z))
{
printf("-1\n");
}
else
lct.change(y,z,x);
}
else
{
if(lct.getroot(x)!=lct.getroot(y))
{
printf("-1\n");
}
else
printf("%d\n",lct.query(x,y));
}
}
printf("\n");
}
}版权声明：本文为博主原创文章，未经博主允许不得转载。
HDOJ 题目4010 Query on The Trees（Link Cut Tree连接，删边，路径点权加，路径点权最大值）
原文：http://blog.csdn.net/yu_ch_sh/article/details/48041477