学了一发LCT，感觉自己萌萌哒~

# include <stdio.h>
# include <algorithm>
 
using namespace std;

const int M=203000;
int fa[M],ch[M][2],sz[M];
long long val[M],sum[M],maxx[M];
bool rev[M];

inline bool isroot(int x) {
	return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;
}
inline long long max(long long a,long long b) {
	return a>b?a:b;
}
inline void pushup(int x) {
	sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x];
	maxx[x]=max(val[x],max(maxx[ch[x][0]],maxx[ch[x][1]]));	
}
inline void pushdown(int x) {
	if(rev[x]) {
		rev[x]^=1;
		rev[ch[x][0]]^=1;
		rev[ch[x][1]]^=1;
		swap(ch[x][0],ch[x][1]);
	}
}
inline void rotate(int x) {
	int y=fa[x],z=fa[y],p=ch[y][1]==x;
	if(!isroot(y)) ch[z][ch[z][1]==y]=x;
	fa[ch[x][p^1]]=y;ch[y][p]=ch[x][p^1];
	fa[y]=x,fa[x]=z;ch[x][p^1]=y;
	pushup(y);
	pushup(x);
}
int q[M*2],qn=0;
inline void splay(int x) {
	q[++qn]=x;
	for (int i=x;!isroot(i);i=fa[i]) q[++qn]=fa[i];
	while(qn) pushdown(q[qn--]);
	while(!isroot(x)) {
		int y=fa[x],z=fa[y];
		if(!isroot(y)) {
			if((ch[y][0]==x)^(ch[z][0]==y)) rotate(x);
			else rotate(y);
		}
		rotate(x);
	}
}
inline void access(int x) {
	for (int t=0;x;t=x,x=fa[x]) splay(x),ch[x][1]=t,pushup(x);
}
inline void makeroot(int x) {
	access(x);splay(x);rev[x]^=1;
}
inline void link(int x,int y) {
	makeroot(x);fa[x]=y;
}
inline void getdata(int x,int y) {
	makeroot(x);access(y);splay(y);
}
inline void cut(int x,int y) {
	getdata(x,y);ch[y][0]=fa[x]=0;
}
int n,u[M],v[M],Q;char opt[9];
int main() {
	scanf("%d",&n);maxx[0]=-200011300;
	for (int i=1;i<n;++i) scanf("%d%d",&u[i],&v[i]);
	for (int i=1;i<=n;++i) scanf("%lld",&val[i]),maxx[i]=sum[i]=val[i];
	for (int i=1;i<n;++i) link(u[i],v[i]);
	scanf("%d",&Q);
	while(Q--) {
		scanf("%s",opt);
		int ly,cdl;
		scanf("%d%d",&ly,&cdl);
		if(opt[1]=='H') splay(ly),val[ly]=cdl,pushup(ly);
		if(opt[1]=='S') getdata(ly,cdl),printf("%lld\n",sum[cdl]);
		if(opt[1]=='M') getdata(ly,cdl),printf("%lld\n",maxx[cdl]);
	}
	return 0;
}