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

/****************************************\
* Author : ztx
* Title  : [bzoj] 1036: [ZJOI2008]树的统计Count
* ALG    : LCT复习  平衡树写的spaly
* CMT    :
单点修改,链查询max,sum
* Time   :
\****************************************/

#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
typedef long long ll ;
int CH , NEG ;
template <typename TP>inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}
template <typename TP>inline void reads(TP& ret) {
	while (ret=getchar() , ret<'!') ;
	while (ret=CH,CH=getchar() , CH>'!') ;
}

#define  maxn  30010LL

int fa[maxn] = {0} , ch[maxn][2] = {0} ;
int val[maxn] = {0} , maxv[maxn] = {0} , sumv[maxn] = {0} ;
bool rev[maxn] = {0} ;

#define  null     0LL
#define  left(u)  ch[u][0]
#define  right(u) ch[u][1]

inline void Exchange(int&a,int&b) {int c=a;a=b;b=c;}
inline bool Isrt(int u) { return !fa[u] || (left(fa[u])!=u&&right(fa[u])!=u) ; }
inline void Clear(int u) {
	if (!u) return ;
	if (rev[u]) {
		rev[u] = false ;
		Exchange(left(u),right(u)) ;
		rev[left(u)] ^= true ;
		rev[right(u)] ^= true ;
	}
}
inline void Maintain(int u) {
	if (!u) return ;
	sumv[u] = maxv[u] = val[u] ;
	if (left(u)) {
		sumv[u] += sumv[left(u)] ;
		if (maxv[left(u)] > maxv[u]) maxv[u] = maxv[left(u)] ;
	}
	if (right(u)) {
		sumv[u] += sumv[right(u)] ;
		if (maxv[right(u)] > maxv[u]) maxv[u] = maxv[right(u)] ;
	}
}
inline void Rot(int x , int d) {
	int y = fa[x] , z = fa[y] ;
	if (left(z)==y) left(z) = x ;
	else if (right(z)==y) right(z) = x ;
	fa[x] = z , fa[ch[x][d]] = y , ch[y][!d] = ch[x][d] ;
	ch[x][d] = y , fa[y] = x ;
	Maintain(y) ;
}
/*
inline void Spaly(int x) {
	Clear(x) ;
	while (!Isrt(x))
		Clear(fa[x]),Clear(x),Rot(x,ch[fa[x]][0]==x) ;
	Maintain(x) ;
}*/
inline void Spaly(int x){
	int y , z ;
	Clear(x) ;
	while (!Isrt(x)) {
		y = fa[x] , z = fa[y] ;
		Clear(z) , Clear(y) , Clear(x) ;
		if (Isrt(y)) Rot(x,ch[y][0]==x) ;
		else if(ch[z][0] == y) {
			if (ch[y][0] == x) Rot(y,1) ;
			else Rot(x,0) ; Rot(x,1) ;
		} else {
			if(ch[y][1] == x) Rot(y,0) ;
			else Rot(x,1) ; Rot(x,0) ;
		}
	}
	Maintain(x) ;
}

inline void Access(int u) {
	for (int v=null ; u ; v=u,u=fa[u]) Spaly(u), right(u)=v, Maintain(u) ;
}
inline void MakeRoot(int u) {
	Access(u) , Spaly(u) , rev[u] ^= true ;
}
inline void ChainMax(int u , int v) {
	MakeRoot(u) , Access(v) , Spaly(v) ;
	printf("%d\n", maxv[v]) ;
}
inline void ChainSum(int u , int v) {
	MakeRoot(u) , Access(v) , Spaly(v) ;
	printf("%d\n", sumv[v]) ;
}
inline void NodeChange(int u , int v) {
	Spaly(u) ; val[u] = v ; Maintain(u) ;
}

#define  maxm  30010LL

struct FST { int to , next ; } e[maxm<<1] ;
int star[maxn] = {0} , tote = 1 ;
inline void AddEdge(int u , int v) { e[++tote].to = v ; e[tote].next = star[u] ; star[u] = tote ; }
inline void GetPar(int u) {
	for (int p=star[u] ; p ; p=e[p].next)
		if (e[p].to != fa[u])
			fa[e[p].to] = u , GetPar(e[p].to) ;
}

int main() {
int n , m , i , u , v , cmd ;
	#define READ
	#ifdef  READ
		freopen("bzoj_1036.in" ,"r",stdin ) ;
		freopen("bzoj_1036.out","w",stdout) ;
	#endif
	read(n) ;
	Rep (i,2,n)
		read(u) , read(v) ,
		AddEdge(u,v) , AddEdge(v,u) ;
	Rep (i,1,n)
		read(val[i]) , maxv[i] = sumv[i] = val[i] ;
	GetPar(1) ;
	read(m) ;
	while (m --> 0) {
		reads(cmd) , read(u) , read(v) ;
		if (cmd == 'E') NodeChange(u,v) ;
		if (cmd == 'X') ChainMax(u,v) ;
		if (cmd == 'M') ChainSum(u,v) ;
	}
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}