记录编号	159931	评测结果	AAAAAAAAAA
题目名称	[ZJOI 2008]树的统计Count	最终得分	100
用户昵称	JSX	是否通过	通过
代码语言	C++	运行时间	1.369 s
提交时间	2015-04-23 11:48:49	内存使用	1.58 MiB

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
template<class T>inline void Read(T& x) {
	x = 0; bool flag = 0; char ch = getchar();
	while(ch<'0'||ch>'9') { if(ch == '-') flag = 1; ch = getchar(); }
	while('0'<=ch&&ch<='9') { x=x*10+ch-'0'; ch = getchar(); }
	if(flag) x=-x;
}
#define maxn 30100
struct node{ int to,next; }E[maxn << 1];
int line[maxn],tot = 0;
inline void insert(int x,int y) {
	tot ++; E[tot].to = y; E[tot].next = line[x]; line[x] = tot;
}
int fa[maxn],maxx[maxn],sum[maxn],ch[maxn][2],val[maxn];
bool rev[maxn];
#define L(o) ch[o][0]
#define R(o) ch[o][1]
inline void update(int x) {
	sum[x] = sum[L(x)] + sum[R(x)] + val[x];
	maxx[x] = max(val[x],max(maxx[L(x)],maxx[R(x)]));
}
inline void pushdown(int x) {
	if(!x) return;
	if(rev[x]) {
		rev[x] = 0;
		swap(L(x),R(x));
		rev[L(x)] ^= 1; rev[R(x)] ^= 1;
	}
}
inline bool IsRoot(int x) {
	return (fa[x] == 0) || (L(fa[x]) != x && R(fa[x]) != x);
}
inline void rotate(int x,bool d) {
	int y = fa[x],z = fa[y];
	if(L(z) == y) L(z) = x; else if(R(z) == y) R(z) = x;
	fa[x] = z; fa[ch[x][d]] = y; ch[y][d^1] = ch[x][d]; ch[x][d] = y; fa[y] = x;
	update(y);
}
inline void splay(int x) {
	pushdown(x);
	int y = 0,z = 0;
	while(!IsRoot(x)) {
		y = fa[x]; z = fa[y];
		pushdown(z); pushdown(y); pushdown(x);
		if(IsRoot(y)) rotate(x,L(y) == x);
		else {
			if(L(z) == y) {
				if(L(y) == x) rotate(y,1);
				else rotate(x,0);
				rotate(x,1);
			} else {
				if(R(y) == x) rotate(y,0);
				else rotate(x,1);
				rotate(x,0);
			}
		} 
	}
	update(x);
}
inline void access(int u) {
	for(int v = 0;u != 0;u = fa[u]) {
		splay(u); R(u) = v; v = u; update(u);
	}
} 
inline void make_root(int x) {
	access(x); splay(x); rev[x] ^= 1;
}
int n = 0,m = 0;
inline void dfs(int x) {
	for(int i = line[x];i != 0;i = E[i].next) {
		if(E[i].to != fa[x]) {
			fa[E[i].to] = x; dfs(E[i].to);
		}
	}
}
int main() {
	freopen("bzoj_1036.in","r",stdin);
	freopen("bzoj_1036.out","w",stdout);
	Read(n);
	int x = 0,y = 0;
	for(int i = 1;i < n;++ i) {
		Read(x); Read(y);
		insert(x,y); insert(y,x);
	}
	for(int i = 1;i <= n;++ i) Read(val[i]);
	dfs(1); maxx[0] = -100000;
	Read(m); char op[10]; 
	while(m --> 0) {
		scanf("%s",op); Read(x); Read(y);
		if(op[0] == 'C') {
			splay(x); val[x] = y; update(x);
		} else {
			make_root(x); access(y); splay(y);
			if(op[1] == 'S') {
				printf("%d\n",sum[y]);
			} else {
				printf("%d\n",maxx[y]);
			}
		}
	}
	return 0;
}