【ZJOI2008】树的统计(LCT)做法

原题

一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。
我们将以下面的形式来要求你对这棵树完成一些操作：
①. CHANGE u t : 把结点u的权值改为t
②. QMAX u v: 询问从点u到点v的路径上的节点的最大权值
③. QSUM u v: 询问从点u到点v的路径上的节点的权值和
注意：从点u到点v的路径上的节点包括u和v本身
此题也可以在bzoj上提交。题号1036。

题解

由于此题的树链剖分做法我已经很娴熟，所以想尝试一下LCT做法。
若要求一条链的某些值，可以只将这条链放置于树顶，这条链连成的边是重边，其他与这条链连着的边为轻边。
那么对于$(x,y)$直接$Makeroot(x)$，然后$Access(y)$，再将y旋到根，那么y点上的值就是想要的答案。

代码

#include
#include
#include
#include
#include
#define N 30010
#define Null 30005
#define P(a) putchar(a)
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
struct note{int to,next;
};note edge[N*2];
int tot,head[N]; 
struct sp{int f,c[2];int sum,mx,tag;
};sp tr[N];
int i,j,k,l,n,m,q,root;
int u,v;
int val[N];
int stack[N];
char ch;
void lb(int x,int y){edge[++tot].to=y;edge[tot].next=head[x];head[x]=tot;}
int read(){int res=0,fh=1;char ch;while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();while(ch=='-')fh=-1,ch=getchar();while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();return res*fh;
}
void write(int x){if(x>9)write(x/10);P(x%10+'0');
}
void Write(int x){if(x<0)P('-'),x=-x;write(x);
}
void dg(int x){for(int i=head[x];i;i=edge[i].next)if(edge[i].to!=tr[x].f){tr[edge[i].to].f=x;dg(edge[i].to);}
}
bool isRoot(int x){return tr[tr[x].f].c[0]!=x&&tr[tr[x].f].c[1]!=x;}
void update(int x){tr[x].mx=max(max(tr[tr[x].c[0]].mx,tr[tr[x].c[1]].mx),val[x]);tr[x].sum=tr[tr[x].c[0]].sum+tr[tr[x].c[1]].sum+val[x];
}
void pdw(int x){if(tr[x].tag){tr[tr[x].c[0]].tag^=1;tr[tr[x].c[1]].tag^=1;swap(tr[x].c[0],tr[x].c[1]);tr[x].tag=0;}
}
int dir(int x){return tr[tr[x].f].c[1]==x;}
void sc(int ps,int nw,int z){tr[ps].c[z]=nw;if(nw!=Null)tr[nw].f=ps;
}
void zig(int x){int y=tr[x].f,z=dir(x),w=tr[y].f;sc(y,tr[x].c[z^1],z);if(!isRoot(y))sc(tr[y].f,x,dir(y));sc(x,y,z^1);tr[x].f=w; update(y),update(x);
}
void splay(int x){int i,top=0;stack[++top]=x;for(i=x;!isRoot(i);i=tr[i].f)stack[++top]=tr[i].f;while(top)pdw(stack[top--]);while(!isRoot(x)){int y=tr[x].f;if(!isRoot(y))if(dir(x)==dir(y))zig(y);else zig(x);zig(x);}update(x);
}
void access(int x){for(int y=Null;x!=Null;x=tr[x].f){splay(x);tr[x].c[1]=y;y=x;}
}
void makeroot(int x){access(x);splay(x);tr[x].tag^=1;
}
void change(int x,int y){splay(x);val[x]=y;update(x);
}
int main(){n=read();fo(i,1,n-1){u=read(),v=read();lb(u,v);lb(v,u);}fo(i,1,n)tr[i].c[0]=tr[i].c[1]=Null;fo(i,1,n){val[i]=read();tr[i].mx=tr[i].sum=val[i];}tr[1].f=Null;tr[Null].mx=-2147483647;dg(1);q=read();while(q--){ch=getchar();ch=getchar();u=read(),v=read();if(ch=='S'||ch=='M'){makeroot(u);access(v);splay(v);if(ch=='S')Write(tr[v].sum);else Write(tr[v].mx);P('\n');} else change(u,v);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！