记录编号	156873	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2008]树的统计Count	最终得分	100
用户昵称	new ioer	是否通过	通过
代码语言	C++	运行时间	2.253 s
提交时间	2015-04-06 18:45:51	内存使用	1.40 MiB

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=30010,maxm=60010;
int c[maxn][2],fa[maxn],val[maxn],sum[maxn],mmax[maxn];
bool vis[maxn],rev[maxn];
vector <int> g[maxn];
bool isrt(int x){
	return (!fa[x])||(c[fa[x]][0]!=x&&c[fa[x]][1]!=x);
}
void update(int x){
	sum[x]=sum[c[x][0]]+sum[c[x][1]]+val[x];
	mmax[x]=max(val[x],max(mmax[c[x][0]],mmax[c[x][1]]));
}
void pushdown(int x){
	if(!x) return;
	if(!rev[x]) return;
	rev[x]=0,swap(c[x][0],c[x][1]);
	rev[c[x][0]]^=1,rev[c[x][1]]^=1;
}
void dfs(int x){
	vis[x]=1;
	for(int i=g[x].size()-1;~i;i--)
		if(!vis[g[x][i]])
			fa[g[x][i]]=x,dfs(g[x][i]);
}
void rot(int x,bool d){
	int y=fa[x],z=fa[y];
	if(c[z][0]==y) c[z][0]=x;
	else if(c[z][1]==y) c[z][1]=x;
	fa[x]=z,fa[c[x][d]]=y,c[y][!d]=c[x][d],c[x][d]=y,fa[y]=x;
	update(y);
}
void splay(int x){
	pushdown(x);
	while(!isrt(x))
		pushdown(fa[x]),pushdown(x),rot(x,c[fa[x]][0]==x);
	update(x);
}
void access(int u){
	for(int v=0;u;u=fa[u])
		splay(u),c[u][1]=v,v=u,update(u);
}
int main(){
	freopen("bzoj_1036.in","r",stdin);
	freopen("bzoj_1036.out","w",stdout);
	int n,m,x,y;
	char str[10];
	scanf("%d",&n);
	for(int u,v,i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1),mmax[0]=-100000;
	for(int i=1;i<=n;i++) scanf("%d",&val[i]);
	scanf("%d",&m);
	while(m--){
		scanf("%s%d%d",str,&x,&y);
		if(str[0]=='C') splay(x),val[x]=y,update(x);
		else{
			access(x),splay(x),rev[x]^=1,access(y),splay(y);
			if(str[1]=='S') printf("%d\n",sum[y]);
			else printf("%d\n",mmax[y]);
		}
	}
}