记录编号	360701	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2008]树的统计Count	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	2.119 s
提交时间	2016-12-31 11:09:26	内存使用	1.57 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define isroot(x) ((x)->p==null||((x)->p->ch[0]!=(x)&&(x)->p->ch[1]!=(x)))
#define dir(x) ((int)((x)==(x)->p->ch[1]))
using namespace std;
const int maxn=30010;
struct node{
	int data,sm,mx;
	node *ch[2],*p;
	bool rev;
	node(int d=0):data(d),sm(d),mx(d),rev(false){}
	void pushdown(){
		if(!rev)return;
		ch[0]->rev^=true;
		ch[1]->rev^=true;
		swap(ch[0],ch[1]);
		rev=false;
	}
	void refresh(){
		sm=ch[0]->sm+ch[1]->sm+data;
		mx=max(data,max(ch[0]->mx,ch[1]->mx));
	}
}nodes[maxn],*null=nodes;
void dfs(int);
void modify(node*,int);
int qsum(node*,node*);
int qmax(node*,node*);
node *access(node*);
void makeroot(node*);
void splay(node*);
void rot(node*,int);
vector<int>G[maxn];
int n,m,prt[maxn]={0},x,y;
char c[15];
int main(){
	freopen("bzoj_1036.in","r",stdin);
	freopen("bzoj_1036.out","w",stdout);
	null->ch[0]=null->ch[1]=null->p=null;
	null->sm=0;
	null->mx=-2147483647;
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	dfs(1);
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		nodes[i]=node(x);
		nodes[i].ch[0]=nodes[i].ch[1]=null;
		nodes[i].p=nodes+prt[i];
	}
	scanf("%d",&m);
	while(m--){
		scanf("%s%d%d",c,&x,&y);
		if(*c=='C')modify(nodes+x,y);
		else if(c[1]=='M')printf("%d\n",qmax(nodes+x,nodes+y));
		else printf("%d\n",qsum(nodes+x,nodes+y));
	}
	return 0;
}
void dfs(int x){
	for(int i=0;i<(int)G[x].size();i++)if(G[x][i]!=prt[x]){
		prt[G[x][i]]=x;
		dfs(G[x][i]);
	}
}
void modify(node *x,int d){
	makeroot(x);
	x->data=d;
	x->refresh();
}
int qsum(node *x,node *y){
	makeroot(x);
	return access(y)->sm;
}
int qmax(node *x,node *y){
	makeroot(x);
	return access(y)->mx;
}
node *access(node *x){
	node *y=null;
	while(x!=null){
		splay(x);
		x->ch[1]=y;
		(y=x)->refresh();
		x=x->p;
	}
	return y;
}
void makeroot(node *x){
	access(x);
	splay(x);
	x->rev^=true;
}
void splay(node *x){
	x->pushdown();
	while(!isroot(x)){
		if(!isroot(x->p))x->p->p->pushdown();
		x->p->pushdown();
		x->pushdown();
		if(isroot(x->p)){
			x->p->p->pushdown();
			rot(x->p,dir(x)^1);
			break;
		}
		if(dir(x)==dir(x->p))rot(x->p->p,dir(x->p)^1);
		else rot(x->p,dir(x)^1);
		rot(x->p,dir(x)^1);
	}
}
void rot(node *x,int d){
	node *y=x->ch[d^1];
	x->ch[d^1]=y->ch[d];
	if(y->ch[d]!=null)y->ch[d]->p=x;
	y->p=x->p;
	if(!isroot(x))x->p->ch[dir(x)]=y;
	y->ch[d]=x;
	x->p=y;
	x->refresh();
	y->refresh();
}