记录编号	408021	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2008]树的统计Count	最终得分	100
用户昵称	半汪	是否通过	通过
代码语言	C++	运行时间	2.925 s
提交时间	2017-05-23 18:32:41	内存使用	1.46 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=30010;
int son[maxn][2],v[maxn],qsum[maxn],qmax[maxn],tag[maxn],fa[maxn],n,m,s[maxn],top,from[maxn],to[maxn];
#define L(x) son[x][0]
#define R(x) son[x][1]
void check(){
    for(int i=1;i<=n;i++)cout<<i<<" "<<fa[i]<<" "<<L(i)<<" "<<R(i)<<" "<<qmax[i]<<" "<<qsum[i]<<endl;
}
bool isroot(int x){
    if(!fa[x])return 1;
    if(L(fa[x])==x||R(fa[x])==x)return 0;
    return 1;
}
void update(int x){
    if(!x)return ;
    qsum[x]=qsum[L(x)]+qsum[R(x)]+v[x];
    qmax[x]=v[x];
    if(L(x))qmax[x]=max(qmax[x],qmax[L(x)]);
    if(R(x))qmax[x]=max(qmax[x],qmax[R(x)]);
}
void pushdown(int x){
    if(!x||!tag[x])return;
    tag[L(x)]^=1;
    tag[R(x)]^=1;
    swap(L(x),R(x));
   // cout<<x<<" "<<L(x)<<" "<<R(x)<<endl;
    tag[x]=0;
}
void rotate(int x,int k){
    int y=son[x][k^1];
    son[x][k^1]=son[y][k];
    son[y][k]=x;
    fa[son[x][k^1]]=x;
    if(L(fa[x])==x)L(fa[x])=y;
    else if(R(fa[x])==x)R(fa[x])=y;
    fa[y]=fa[x];fa[x]=y;
    update(x);update(y);
   // cout<<"rotate"<<x<<" "<<k<<endl;
}
void splay(int x){
   // cout<<x<<endl;
    s[++top]=x;
    for(int i=x;!isroot(i);i=fa[i])s[++top]=fa[i];
    while(top)pushdown(s[top--]);
    int y,z;
 //   cout<<x<<"!"<<fa[x]<<" "<<R(2)<<" "<<isroot(x)<<endl;
    while(!isroot(x)){
      //  cout<<x<<endl;
        y=fa[x],z=fa[y];
        if(isroot(y))rotate(y,L(y)==x);
        else{
            if((L(y)==x)==(L(z)==y))rotate(z,L(z)==y),rotate(y,L(y)==x);
            else rotate(y,L(y)==x),rotate(z,L(z)==x);
        }
    }update(x);
   // cout<<x<<" * "<<L(x)<<" "<<R(x)<<endl;
} 
void access(int x){
    int y=0;
    while(x){
     //   cout<<x<<" "<<y<<endl;
        splay(x);
        R(x)=y;
        update(x);
        y=x;
        x=fa[x];
    }
}
void makeroot(int x){
    access(x);
  //  cout<<"had accessed"<<endl;
   // check();
  //  cout<<2<<" "<<L(2)<<" "<<R(2)<<" "<<fa[1]<<endl;
    splay(x);
    tag[x]^=1;
}
void link(int x,int y){
 //   cout<<x<<"****"<<y<<endl;
    makeroot(x);
    fa[x]=y;
  //  check();
}
void change(int x,int w){
    splay(x);
    v[x]=w;
    qmax[x]=w;
    qsum[x]=w;
    if(L(x))qmax[x]=max(qmax[L(x)],qmax[x]);
    if(R(x))qmax[x]=max(qmax[R(x)],qmax[x]);
    qsum[x]=w+qsum[L(x)]+qsum[R(x)];
}
void querymax(int x,int y){
    makeroot(x);
    access(y);
    splay(x);
    printf("%d\n",qmax[x]);
}
void querysum(int x,int y){
    makeroot(x);
    access(y);
    splay(x);
    printf("%d\n",qsum[x]);
}
int main(){
    freopen("bzoj_1036.in","r",stdin);freopen("bzoj_1036.out","w",stdout);
  //  freopen("1036.in","r",stdin);freopen("1036.out","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        from[i]=x;
        to[i]=y;
    }
    for(int i=1;i<=n;i++)scanf("%d",&v[i]);
    for(int i=1;i<n;i++){
        link(from[i],to[i]);
    }
//    for(int i=1;i<=n;i++)cout<<i<<" "<<fa[i]<<" "<<L(i)<<" "<<R(i)<<" "<<qmax[i]<<" "<<qsum[i]<<endl;
    scanf("%d",&m);
    while(m--){
        char ch[10];
        scanf("%s",ch);
        if(ch[0]=='C'){
            int u,t;
            scanf("%d%d",&u,&t);
            change(u,t);
        }
        if(ch[1]=='M'){
            int u,v;
            scanf("%d%d",&u,&v);
            querymax(u,v);
        }
        if(ch[1]=='S'){
            int u,v;
            scanf("%d%d",&u,&v);
            querysum(u,v);
        }
    }
    return 0;
}