BZOJ1036;[ZJOI2008]树的统计

1036: [ZJOI2008]树的统计Count

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 17649 Solved: 7195
[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

　　没什么,一道水题,只是想用来练一练LCT....

#include<bits/stdc++.h>
#define RG register
#define il inline 
#define N 30010
#define LL long long
using namespace std;
struct ed{int nxt,to;}e[N*2];int head[N],tot;
void add(int u,int v){e[tot].nxt=head[u];e[tot].to=v;head[u]=tot++;}
void ADD(int u,int v){add(u,v),add(v,u);}int fa[N];
void dfs(int u){for(int i=head[u];i!=-1;i=e[i].nxt)if(e[i].to!=fa[u])fa[e[i].to]=u,dfs(e[i].to);}
int Max[N],ch[N][2],st[N],n,v[N];bool rev[N];LL sum[N];
int max(int x,int y){return x>y?x:y;}
bool isroot(int x){return ch[fa[x]][1]!=x&&ch[fa[x]][0]!=x;}
void down(int x){if(rev[x]){rev[x]^=1,rev[ch[x][1]]^=1,rev[ch[x][0]]^=1,swap(ch[x][1],ch[x][0]);}}
void up(int x){sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+v[x],Max[x]=max(max(Max[ch[x][1]],Max[ch[x][0]]),v[x]);}
void Rotate(int x){
  int y=fa[x],z=fa[y],l,r;
  if(ch[y][0]==x)l=0;else l=1;r=l^1;
  if(!isroot(y))ch[z][ch[z][1]==y]=x;
  fa[x]=z,fa[y]=x;fa[ch[x][r]]=y;
  ch[y][l]=ch[x][r],ch[x][r]=y;
  up(y),up(x);
}
void Splay(int x){int y=x;
  int top(0);st[++top]=x;
  while(!isroot(y))st[++top]=fa[y],y=fa[y];
  for(int i=top;i;i--)down(st[i]);
  while(!isroot(x)){
    y=fa[x];int z=fa[y];
    if(!isroot(y)){
      if(ch[z][0]==y^ch[y][0]==x)Rotate(x);
      else Rotate(y);
    }Rotate(x);
  }up(x);
}
void access(int x){
  int t=0;
  while(x){
    Splay(x);
    ch[x][1]=t;
    t=x;
    up(x);
    x=fa[x];
  }
}
void rever(int x){
  access(x);
  Splay(x);
  rev[x]^=1;
}
void querymax(int x,int y){
  rever(x);
  access(y);
  Splay(y);
  cout<<Max[y]<<"
";
}
void querysum(int x,int y){
  rever(x);
  access(y);
  Splay(y);
  cout<<sum[y]<<"
";
}
void change(int x,int kk){Splay(x),v[x]=kk,up(x);}
int main(){
  scanf("%d",&n);int u,V;memset(head,-1,sizeof(head));
  for(int i=2;i<=n;++i)scanf("%d%d",&u,&V),ADD(u,V);Max[0]=-6666666;
  for(int i=1;i<=n;++i)scanf("%d",&v[i]),sum[i]=Max[i]=v[i];;int Q;scanf("%d",&Q);
  char s[6];dfs(1);
  for(int i=1;i<=Q;++i){
    scanf("%s",s);int x,y;scanf("%d%d",&x,&y);
    if(s[0]=='Q'&&s[1]=='M')querymax(x,y);
    else if(s[0]=='Q'&&s[1]=='S')querysum(x,y);
    else change(x,y);
  }return 0;
}