BZOJ1036 [ZJOI2008]树的统计Count

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

解题报告：裸的lct

  1 #include <iostream>
  2 #include <iomanip>
  3 #include <cstdlib>
  4 #include <cstdio>
  5 #include <cmath>
  6 #include <cstring>
  7 #include <string>
  8 #include <algorithm>
  9 #define MAX(a,b) a>b?a:b
 10 #define RG register
 11 #define int long long
 12 const int N = 1000000;
 13 const int inf = 214748364100000000;
 14 
 15 using namespace std;
 16 
 17 inline int gi(){
 18     RG char ch=getchar();RG int x=0,q=0;
 19     while(ch<'0' || ch>'9') {if (ch=='-') q=1;ch=getchar();}
 20     while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
 21     return q?(-x):x;
 22 }
 23 
 24 int fa[N],c[N][2],sum[N],mx[N],rev[N];
 25 int nn[N][2],head[N],cnt,f[N],st[N],vis[N];
 26 char ch[10];
 27 
 28 void dfs(int xh,int fu){
 29     fa[xh]=fu,vis[xh]=1;
 30     for (RG int i=head[xh]; i; i=nn[i][0])
 31         if (vis[nn[i][1]]==0) dfs(nn[i][1],xh);
 32     return;
 33 }
 34 
 35 int isroot(int x){
 36     return c[fa[x]][0]!=x && c[fa[x]][1]!=x;
 37 }
 38 
 39 void pushdown(int x){
 40     if (rev[x]==0) return;
 41     rev[x]^=1,rev[c[x][0]]^=1,rev[c[x][1]]^=1;
 42     swap(c[x][0],c[x][1]);
 43     return;
 44 }
 45 
 46 void update(int x){
 47     RG int ls=c[x][0],rs=c[x][1];
 48     mx[x]=f[x],sum[x]=0;
 49     if (ls) mx[x]=MAX(mx[ls],mx[x]);
 50     if (rs) mx[x]=MAX(mx[rs],mx[x]);
 51     sum[x]=sum[ls]+sum[rs]+f[x];
 52     return;
 53 }
 54 
 55 void rotate(int x){
 56     RG int y=fa[x],z=fa[y],l,r;
 57     if (c[y][0]==x) l=0;else l=1;
 58     r=l^1;
 59     if (!isroot(y))
 60         if (c[z][0]==y) c[z][0]=x;
 61         else c[z][1]=x;
 62     fa[x]=z,fa[y]=x,fa[c[x][r]]=y;
 63     c[y][l]=c[x][r],c[x][r]=y;
 64     update(y),update(x);
 65     return;
 66 }
 67 
 68 void splay(int x){
 69     RG int tot=0;st[++tot]=x;
 70     for (RG int i=x; !isroot(i); i=fa[i]) st[++tot]=fa[i];
 71     for (RG int i=tot; i; --i) pushdown(st[i]);
 72     while(!isroot(x)){
 73         RG int y=fa[x],z=fa[y];
 74         if (!isroot(y))
 75             if (c[z][0]==y ^ c[y][0]==x) rotate(x);
 76             else rotate(y);
 77         rotate(x);
 78     }
 79     return;
 80 }
 81 
 82 void access(int x){
 83     int t=0;
 84     while(x){
 85         splay(x);
 86         c[x][1]=t;
 87         t=x,x=fa[x],update(x);
 88     }
 89     return;
 90 }
 91 
 92 void rever(int x){
 93     access(x),splay(x),rev[x]^=1;
 94     return;
 95 }
 96 
 97 int query_max(int u,int v){
 98     rever(u),access(v),splay(v);
 99     if (c[v][0]) return MAX(mx[c[v][0]],f[v]);
100     return f[v];
101 }
102 
103 int query_sum(int u,int v){
104     rever(u),access(v),splay(v);
105     return sum[c[v][0]]+f[v];
106 }
107 
108 main(){
109     int l,r,n=gi();
110     mx[0]=-inf;
111     for (RG int i=1; i<n; ++i){
112         l=gi(),r=gi();
113         nn[++cnt][1]=l,nn[cnt][0]=head[r],head[r]=cnt;
114         nn[++cnt][1]=r,nn[cnt][0]=head[l],head[l]=cnt;
115     }
116     for (RG int i=1; i<=n; ++i) f[i]=gi(),mx[i]=f[i],sum[i]=f[i];
117     dfs(1,0);
118     int q=gi();
119     for (RG int i=1; i<=q; ++i){
120         scanf("%s",ch);
121         RG int u=gi(),v=gi();
122         if (ch[0]=='C'){
123             splay(u);
124             f[u]=v;
125             update(u);
126         }
127         else if (ch[1]=='M') printf("%lld
",query_max(u,v));
128         else if (ch[1]=='S') printf("%lld
",query_sum(u,v));
129     }
130 }