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

#include<cstdio>
const int maxn=30001;
const int size=65537;
int N,M,Q,cnt,len,g[maxn];
int MAX[size],SUM[size];
int fa[maxn],siz[maxn],top[maxn],son[maxn],dep[maxn],w[maxn],v[maxn];
struct Edge{
	int to,next;
}e[maxn<<1];
int max(int x,int y){
	if(x>y) return x;
	return y;
}
int swap(int &x,int &y){
	x=x^y,y=x^y,x=x^y;
}
void Getz(int &x){
	int ch;
	while(ch=getchar(),ch<48||ch>57);x=ch-48;
	while(ch=getchar(),ch>47&&ch<58) x=x*10+ch-48;
}
void Getf(int &x){
	int ch,flag=0;
	while(ch=getchar(),ch<48||ch>57) if(ch==45) break;
	if(ch==45) x=0,flag=1;
	else x=ch-48;
	while(ch=getchar(),ch>47&&ch<58) x=x*10+ch-48;
	if(flag) x=-x;
}
void Add_Edge(int x,int y){
	e[++len].to=y,e[len].next=g[x],g[x]=len;
}
void DFS1(int x){
	siz[x]=1;
	for(int i=g[x];i;i=e[i].next){
		int t=e[i].to;
		if(t==fa[x]) continue;
		fa[t]=x,dep[t]=dep[x]+1;
		DFS1(t),siz[x]+=siz[t];
		if(siz[t]>siz[son[x]]) son[x]=t;
	}
}
void DFS2(int x,int tp){
	w[x]=++cnt,top[x]=tp,MAX[cnt+M]=SUM[cnt+M]=v[x];
	if(son[x]) DFS2(son[x],tp);
	for(int i=g[x];i;i=e[i].next){
		int t=e[i].to;
		if(t==fa[x]||t==son[x]) continue;
		DFS2(t,t);
	}
}
void Change(int i,int x){
	for(i+=M,SUM[i]=MAX[i]=x,i>>=1;i;i>>=1){
		MAX[i]=max(MAX[i<<1],MAX[(i<<1)^1]);
    	SUM[i]=SUM[i<<1]+SUM[(i<<1)^1];
	}
}
int Sum(int s,int t){
	int sum=0;
	for(s+=M-1,t+=M+1;s^t^1;s>>=1,t>>=1){
		if(~s&1) sum+=SUM[s^1];
		if( t&1) sum+=SUM[t^1];
	}
	return sum;
}
int Max(int s,int t){
	int res=-maxn;
	for(s+=M-1,t+=M+1;s^t^1;s>>=1,t>>=1){
		if(~s&1) res=max(res,MAX[s^1]);
		if( t&1) res=max(res,MAX[t^1]);
	}
	return res;
}
void Qsum(int x,int y){
	int sum=0;
	for(int fx=top[x],fy=top[y];fx!=fy;fx=top[x=fa[fx]]){
		if(dep[fx]<dep[fy]) swap(x,y),swap(fx,fy);
		sum+=Sum(w[fx],w[x]);
	}
	if(dep[x]>dep[y]) swap(x,y);
	printf("%d\n",sum+Sum(w[x],w[y]));
}
void Qmax(int x,int y){
	int res=-maxn;
	for(int fx=top[x],fy=top[y];fx!=fy;fx=top[x=fa[fx]]){
		if(dep[fx]<dep[fy]) swap(x,y),swap(fx,fy);
		res=max(res,Max(w[fx],w[x]));
	}
	if(dep[x]>dep[y]) swap(x,y);
	printf("%d\n",max(res,Max(w[x],w[y])));
}
int main(){
    freopen("bzoj_1036.in","r",stdin);
	freopen("bzoj_1036.out","w",stdout);
	Getz(N);
	for(M=1;M<N+2;M<<=1);
	for(int x,y,i=1;i<N;i++){
		Getz(x),Getz(y);
		Add_Edge(x,y),Add_Edge(y,x);
	}
	for(int i=1;i<=N;i++) Getf(v[i]);
	DFS1(1),DFS2(1,1);
    for(int i=M;i>=1;i--){
    	MAX[i]=max(MAX[i<<1],MAX[(i<<1)^1]);
    	SUM[i]=SUM[i<<1]+SUM[(i<<1)^1];
    }
    Getz(Q);
	while(Q--){
		int ch,x,y;
		while((ch=getchar())<65);
		if(ch=='C') Getz(x),Getf(y),Change(w[x],y);
		else if(getchar()=='S') Getz(x),Getz(y),Qsum(x,y);
		else Getz(x),Getz(y),Qmax(x,y);
	}
}