记录编号	143512	评测结果	AAAAAAAAAA
题目名称	1688.[ZJOI 2008]树的统计Count	最终得分	100
用户昵称	JSX	是否通过	通过
代码语言	C++	运行时间	0.682 s
提交时间	2014-12-15 16:11:44	内存使用	3.49 MiB

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;
const int MAXN = 30010;

int N=0,Q=0,M1=1;
struct node{
	int to,next;
}E[MAXN<<1];
int line[MAXN]={0},tot=0;
inline void Insert(int x,int y){
	tot++; E[tot].to=y; E[tot].next=line[x]; line[x]=tot;
}

inline int Read() {
	int ret,neg;	char ch;
	ret = neg = 0 ; while (!isdigit(ch=getchar())&&ch!='-') ;
	if (ch=='-') neg = 1 , ch=getchar() ;
	while (ret = ret*10+ch-'0' , isdigit(ch=getchar())) ;
	if (neg) ret = -ret ;
	return ret ;
}

int Sum[MAXN<<3]={0},Max[MAXN<<3]={0};
int W[MAXN]={0},Deep[MAXN]={0},Son[MAXN]={0},Fa[MAXN]={0};
int Size[MAXN]={0},ID[MAXN]={0},Top[MAXN]={0};
inline void DFS1(int u){
	Size[u]=1; Son[u]=0;
	for(int i=line[u];i!=0;i=E[i].next){
		int p=E[i].to;
		if(p!=Fa[u]){
			Fa[p]=u; Deep[p]=Deep[u]+1;
			DFS1(p);
			Size[u]+=Size[p];
			if(Size[p]>Size[Son[u]]) Son[u]=p;
		}
	}
}

int cnt=0;
inline void DFS2(int u,int top){
	ID[u]=++cnt; Top[u]=top; Sum[cnt+M1]=Max[cnt+M1]=W[u];
	if(Son[u]) DFS2(Son[u],top);
	for(int i=line[u];i!=0;i=E[i].next){
		int p=E[i].to;
		if(p!=Fa[u] && p!=Son[u]) DFS2(p,p);
	}
}

inline void Updata(int x,int v){
	x+=M1; Sum[x]=v; Max[x]=v;
	for(x>>=1;x;x>>=1){
		Sum[x]=Sum[(x<<1)]+Sum[(x<<1)+1];
		Max[x]=max(Max[(x<<1)],Max[(x<<1)+1]);
	}
} 

inline int Query_Sum(int s,int t){
	int Ans=0;
	for(s=s+M1-1,t=t+M1+1;s^t^1;s>>=1,t>>=1){
		if(!(s&1)) Ans+=Sum[s^1];
		if( (t&1)) Ans+=Sum[t^1];
	}
	return Ans;
}

inline int Query_Max(int s,int t){
	int Ans=-0x3f3f3f3f;
	for(s=s+M1-1,t=t+M1+1;s^t^1;s>>=1,t>>=1){
		if(!(s&1)) Ans=max(Max[s^1],Ans);
		if( (t&1)) Ans=max(Max[t^1],Ans);
	}
	return Ans;
}

inline int Tree_Sum(int x,int y){
	int fx=Top[x],fy=Top[y],Res=0;
	while(fx!=fy){
		if(Deep[fx]<Deep[fy]){ swap(x,y); swap(fx,fy); }
		Res+=Query_Sum(ID[fx],ID[x]);
		x=Fa[fx]; fx=Top[x];
	}
	if(Deep[x]>Deep[y]) swap(x, y);
    return Res+Query_Sum(ID[x],ID[y]);
}

inline int Tree_Max(int x,int y){
	int fx=Top[x],fy=Top[y],Res=-0x3f3f3f3f;
	while(fx!=fy){
		if(Deep[fx]<Deep[fy]){ swap(x,y); swap(fx,fy); }
		Res=max(Query_Max(ID[fx],ID[x]),Res);
		x=Fa[fx]; fx=Top[x];
	}
	if(Deep[x]>Deep[y]) swap(x, y);
    return max(Res,Query_Max(ID[x],ID[y]));
}

int main(){
	freopen("bzoj_1036.in","r",stdin);
	freopen("bzoj_1036.out","w",stdout);
	N=Read();
	int a=0,b=0;
	for(int i=1;i< N;++i){
		a=Read(); b=Read();
		Insert(a,b); Insert(b,a);
	}
	for(int i=1;i<=N;++i) W[i]=Read();
	for(M1=1;M1<N+2;M1<<=1);
	DFS1(1);
	DFS2(1,1);
	//for(int i=1;i<=N;++i) printf("%d  ",Max[i+M1]);printf("\n");
	//for(int i=1;i<=N;++i) printf("%d  ",ID[i]); printf("\n");
	for(int i=M1;i>=1;--i){
		Sum[i]=Sum[(i<<1)]+Sum[(i<<1)+1];
		Max[i]=max(Max[(i<<1)],Max[(i<<1)+1]);
	}
	Q=Read();
	char s[10];
	for(int i=1;i<=Q;++i){
		scanf("%s",s);
		a=Read(); b=Read();
		if(s[0]=='C')   Updata(ID[a],b);
	    if(s[1]=='S'){
	        printf("%d\n",Tree_Sum(a,b));
	    }
	    if(s[1]=='M'){    
	        printf("%d\n",Tree_Max(a,b));
	    }
	}
	return 0;
}