数据结构（LCT动态树）：BZOJ 1036: [ZJOI2008]树的统计Count

1036: [ZJOI2008]树的统计Count

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 12266 Solved: 4945
[Submit][Status][Discuss]

Description

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

Input

　　输入的第一行为一个整数n，表示节点的个数。接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有
一条边相连。接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。接下来1行，为一个整数q，表示操作
的总数。接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。
对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。

Output

　　对于每个“QMAX”或者“QSUM”的操作，每行输出一个整数表示要求输出的结果。

Sample Input

4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

Sample Output

4
1
2
2
10
6
5
6
5
16

　　模板题，权当复习……

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 using namespace std;

 const int maxn=;

 const int INF=;

 int n,Q;

 bool rt[maxn];

 long long sum[maxn];

 int ch[maxn][],fa[maxn];

 int Mx[maxn],key[maxn],flip[maxn];

 int cnt,fir[maxn],nxt[maxn<<],to[maxn<<];

 void addedge(int a,int b){

     nxt[++cnt]=fir[a];fir[a]=cnt;to[cnt]=b;

 }

 void Push_up(int x){

     sum[x]=sum[ch[x][]]+sum[ch[x][]]+key[x];

     Mx[x]=max(max(Mx[ch[x][]],Mx[ch[x][]]),key[x]);

 }

 void Flip(int x){

     swap(ch[x][],ch[x][]);

     flip[x]^=;

 }

 void Push_down(int x){

     if(flip[x]){

         Flip(ch[x][]);

         Flip(ch[x][]);

         flip[x]=;

     }

 }

 void Rotate(int x){

     int y=fa[x],g=fa[y],c=ch[y][]==x;

     ch[y][c]=ch[x][c^];fa[ch[y][c]]=y;

     ch[x][c^]=y;fa[y]=x;fa[x]=g;

     if(rt[y])rt[y]=false,rt[x]=true;

     else ch[g][ch[g][]==y]=x;

     Push_up(y);

 }

 void P(int x){

     if(!rt[x])P(fa[x]);

     Push_down(x);

 }

 void Splay(int x){

     P(x);

     for(int y=fa[x];!rt[x];Rotate(x),y=fa[x])

         if(!rt[y])Rotate((ch[fa[y]][]==y)==(ch[y][]==x)?y:x);

     Push_up(x);

 }

 void Access(int x){

     int y=;

     while(x){

         Splay(x);

         rt[ch[x][]]=true;

         rt[ch[x][]=y]=false;

         Push_up(x);

         x=fa[y=x];

     }

 }

 void Lca(int &x,int &y){

     Access(y);y=;

     while(true){

         Splay(x);

         if(!fa[x])return;

         rt[ch[x][]]=true;

         rt[ch[x][]=y]=false;

         Push_up(x);

         x=fa[y=x];

     }

 }    

 void Change(int x,int y){

     Splay(x);

     key[x]=y;

     Push_up(x);

 }

 void DFS(int x){

     for(int i=fir[x];i;i=nxt[i])

         if(fa[x]!=to[i]){

             fa[to[i]]=x;

             DFS(to[i]);

         }

 }

 char op[];

 int main(){

     Mx[]=-INF;

     scanf("%d",&n);

     for(int i=,a,b;i<n;i++){

         scanf("%d%d",&a,&b);

         addedge(a,b);

         addedge(b,a);

     }

     for(int i=;i<=n;i++){

         scanf("%d",&key[i]);

         rt[i]=true;

     }

     DFS();

     scanf("%d",&Q);

     int x,y;

     while(Q--){

         scanf("%s",op);

         if(op[]=='C'){

             scanf("%d%d",&x,&y);

             Change(x,y);

         }

         else{

             scanf("%d%d",&x,&y);Lca(x,y);

             if(op[]=='M')

                 printf("%d\n",max(max(key[x],Mx[ch[x][]]),Mx[y]));

             else

                 printf("%lld\n",(long long)(key[x]+sum[ch[x][]]+sum[y]));

         }

     }

     return ;

 }

巴特西