记录编号	143946	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2008]树的统计Count	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.622 s
提交时间	2014-12-19 08:57:33	内存使用	1.12 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int SIZEN=30010,INF=0x7fffffff/2;
inline int max(int a,int b,int c){return max(max(a,b),c);}
class Node{
public:
	int lc,rc,fa;
	int val,sum,mx;
	bool inv;
	void clear(void){
		lc=rc=fa=0;
		val=sum=0;mx=-INF;
		inv=0;
	}
	Node(void){clear();}
	#define lc(x) Tree[x].lc
	#define rc(x) Tree[x].rc
	#define fa(x) Tree[x].fa
	#define val(x) Tree[x].val
	#define sum(x) Tree[x].sum
	#define mx(x) Tree[x].mx
	#define inv(x) Tree[x].inv
};
Node Tree[SIZEN];
bool Is_Root(int x){return lc(fa(x))!=x&&rc(fa(x))!=x;}
void Push_Down(int x){
	if(!x) return;
	if(inv(x)){
		swap(lc(x),rc(x));
		inv(lc(x))^=1;
		inv(rc(x))^=1;
		inv(x)=false;
	}
}
void Update(int x){
	if(!x) return;
	sum(x)=sum(lc(x))+sum(rc(x))+val(x);
	mx(x)=max(mx(lc(x)),mx(rc(x)),val(x));
}
void Zig(int x){//右旋
	int y=fa(x),z=fa(y);
	if(lc(z)==y) lc(z)=x;
	if(rc(z)==y) rc(z)=x;
	fa(x)=z;
	lc(y)=rc(x);fa(lc(y))=y;
	rc(x)=y;fa(y)=x;
	Update(y);Update(x);
}
void Zag(int x){//左旋
	int y=fa(x),z=fa(y);
	if(lc(z)==y) lc(z)=x;
	if(rc(z)==y) rc(z)=x;
	fa(x)=z;
	rc(y)=lc(x);fa(rc(y))=y;
	lc(x)=y;fa(y)=x;
	Update(y);Update(x);
}
void Splay(int x){
	Push_Down(x);
	while(!Is_Root(x)){
		int y=fa(x),z=fa(y);
		Push_Down(z);Push_Down(y);Push_Down(x);
		if(Is_Root(y)){
			if(lc(y)==x) Zig(x);
			else Zag(x);
			return;
		}
		if(lc(z)==y){
			if(lc(y)==x) Zig(y),Zig(x);
			else Zag(x),Zig(x);
		}
		else{
			if(rc(y)==x) Zag(y),Zag(x);
			else Zig(x),Zag(x);
		}
	}
}
void Access(int x){
	int y=0;
	while(x){
		Splay(x);
		rc(x)=y;
		Update(x);
		y=x;
		x=fa(x);
	}
}
void Make_Root(int x){
	Access(x);
	Splay(x);
	inv(x)^=1;
}
void Link(int x,int y){
	Make_Root(x);
	fa(x)=y;
}
int Query_Max(int x,int y){
	Make_Root(x);
	Access(y);
	Splay(y);
	return mx(y);
}
int Query_Sum(int x,int y){
	Make_Root(x);
	Access(y);
	Splay(y);
	return sum(y);
}
void Change_Node(int x,int t){
	Access(x);
	Splay(x);
	val(x)=t;
	Update(x);
}
int N,Q;
void Process(void){
	scanf("%d",&Q);
	char cmd[10];
	int a,b;
	for(int i=1;i<=Q;i++){
		scanf("%s",cmd);
		scanf("%d%d",&a,&b);
		if(cmd[0]=='C') Change_Node(a,b);
		else if(cmd[1]=='M') printf("%d\n",Query_Max(a,b));
		else if(cmd[1]=='S') printf("%d\n",Query_Sum(a,b));
	}
}
void Init(void){
	scanf("%d",&N);
	int a,b,w;
	for(int i=1;i<N;i++){
		scanf("%d%d",&a,&b);
		Link(a,b);
	}
	for(int i=1;i<=N;i++){
		scanf("%d",&w);
		Change_Node(i,w);
	}
}
int main(){
	freopen("bzoj_1036.in","r",stdin);
	freopen("bzoj_1036.out","w",stdout);
	Init();
	Process();
	return 0;
}