记录编号	268602	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2008]树的统计Count	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	1.339 s
提交时间	2016-06-12 16:43:25	内存使用	2.21 MiB

#include<cstdio>
#define lch(x) x<<1
#define rch(x) x<<1|1
const int maxn=30005;int n;
struct edge{
	int to,next;
}lst[maxn<<1];int len=1;
int first[maxn];
void addedge(int a,int b){
	lst[len].to=b;
	lst[len].next=first[a];
	first[a]=len++;
}
int max(int a,int b){
	return a>b?a:b;
}
int Max[maxn<<2],sum[maxn<<2];
void insert(int rt,int l,int r,int k,int w){
	if(r==k&&l==k){
		Max[rt]=sum[rt]=w;
		return;
	}
	int mid=(l+r)>>1;
	if(k<=mid)insert(lch(rt),l,mid,k,w);
	else insert(rch(rt),mid+1,r,k,w);
	Max[rt]=max(Max[lch(rt)],Max[rch(rt)]);
	sum[rt]=sum[lch(rt)]+sum[rch(rt)];
}
int w[maxn],_s[maxn],depth[maxn],top[maxn],fa[maxn],dic[maxn];int T;
void dfs1(int x){
	_s[x]=1;
	for(int pt=first[x];pt;pt=lst[pt].next){
		if(lst[pt].to==fa[x])continue;
		fa[lst[pt].to]=x;
		depth[lst[pt].to]=depth[x]+1;
		dfs1(lst[pt].to);
		_s[x]+=_s[lst[pt].to];
	}
}
void dfs2(int x){
	dic[x]=++T;
	insert(1,1,n,dic[x],w[x]);
	int hvyson=0;
	for(int pt=first[x];pt;pt=lst[pt].next){
		if(lst[pt].to==fa[x])continue;
		if(_s[lst[pt].to]>_s[hvyson])hvyson=lst[pt].to;
	}
	if(hvyson){
		top[hvyson]=top[x];
		dfs2(hvyson);
		for(int pt=first[x];pt;pt=lst[pt].next){
			if(lst[pt].to==fa[x]||lst[pt].to==hvyson)continue;
			top[lst[pt].to]=lst[pt].to;
			dfs2(lst[pt].to);
		}
	}
}
int querysum(int rt,int l,int r,int a,int b){
	if(a<=l&&r<=b)return sum[rt];
	int mid=(l+r)>>1;
	if(b<=mid)return querysum(lch(rt),l,mid,a,b);
	if(a>mid)return querysum(rch(rt),mid+1,r,a,b);
	return querysum(lch(rt),l,mid,a,b)+querysum(rch(rt),mid+1,r,a,b);
}
int querymax(int rt,int l,int r,int a,int b){
	if(a<=l&&r<=b)return Max[rt];
	int mid=(l+r)>>1;
	if(b<=mid)return querymax(lch(rt),l,mid,a,b);
	if(a>mid)return querymax(rch(rt),mid+1,r,a,b);
	return max(querymax(lch(rt),l,mid,a,b),querymax(rch(rt),mid+1,r,a,b));
}
int getsum(int u,int v){
	int t1=top[u],t2=top[v];
	int ans=0;
	while(t1!=t2){
		if(depth[t1]<depth[t2]){
			ans+=querysum(1,1,n,dic[t2],dic[v]);
			v=fa[t2];
			t2=top[v];
		}else{
			ans+=querysum(1,1,n,dic[t1],dic[u]);
			u=fa[t1];
			t1=top[u];
		}
	}
	if(depth[u]>depth[v])ans+=querysum(1,1,n,dic[v],dic[u]);
	else ans+=querysum(1,1,n,dic[u],dic[v]);
	return ans;
}
int getmax(int u,int v){
	int t1=top[u],t2=top[v];
	int ans=-100000000;
	while(t1!=t2){
		if(depth[t1]<depth[t2]){
			ans=max(ans,querymax(1,1,n,dic[t2],dic[v]));
			v=fa[t2];
			t2=top[v];
		}else{
			ans=max(ans,querymax(1,1,n,dic[t1],dic[u]));
			u=fa[t1];
			t1=top[u];
		}
	}
	if(depth[u]>depth[v])ans=max(ans,querymax(1,1,n,dic[v],dic[u]));
	else ans=max(ans,querymax(1,1,n,dic[u],dic[v]));
	return ans;
}
int main(){
	freopen("bzoj_1036.in","r",stdin);
	freopen("bzoj_1036.out","w",stdout);
	scanf("%d",&n);
	int a,b;
	for(int i=1;i<n;++i){
		scanf("%d %d",&a,&b);
		addedge(a,b);
		addedge(b,a);
	}
	for(int i=1;i<=n;++i)scanf("%d",w+i);
	int lim=maxn<<2;
	for(int i=1;i<lim;++i)Max[i]=-100000000;
	depth[1]=1;
	dfs1(1);
	top[1]=1;
	dfs2(1);
	int q;scanf("%d",&q);
	char buf[20];
	while(q--){
		scanf("%s %d %d",buf,&a,&b);
		if(buf[0]=='C'){
			insert(1,1,n,dic[a],b);
		}else if(buf[1]=='S'){
			printf("%d\n",getsum(a,b));
		}else{
			printf("%d\n",getmax(a,b));
		}
	}
	fclose(stdin);fclose(stdout);
	return 0;
}