//pair返回的均为<和，最大值> 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e4+10;
inline bool id(const char ch) {
	return ch>='0'&&ch<='9';
} 
inline int read(void) {
	int s=0,f=1;
	char ch=getchar();
	while(!id(ch)) {
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(id(ch)) s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return s*f;
}
struct Edge {
	int to,nxt;
}edge[MAXN*2];
int n,q;
int hd[MAXN],tot;
int size[MAXN],father[MAXN],dep[MAXN],son[MAXN],top[MAXN],seg[MAXN*4],rev[MAXN*4],ks;
int cnt[MAXN*4],v[MAXN*4],mx[MAXN*4],z[MAXN];
inline void add_edge(const int x,const int y) {
	edge[++tot]={y,hd[x]},hd[x]=tot;
	edge[++tot]={x,hd[y]},hd[y]=tot;
	return;
}
inline void dfs1(const int u,const int f) {  
	size[u]=1,father[u]=f,dep[u]=dep[f]+1; 
	for(int e=hd[u],v=edge[e].to;e;e=edge[e].nxt,v=edge[e].to) {
		if(v!=f) { 
			dfs1(v,u);
			size[u]+=size[v];
			if(size[v]>size[son[u]]) son[u]=v; 
		}
	}
	return;
}
inline void dfs2(const int u,const int f) {
	if(son[u]) { 
		seg[son[u]]=++seg[0],rev[seg[0]]=son[u]; 
		top[son[u]]=top[u];
		dfs2(son[u],u);
	}
	for(int e=hd[u],v=edge[e].to;e;e=edge[e].nxt,v=edge[e].to)
		if(!top[v]) {
			seg[v]=++seg[0],rev[seg[0]]=v;
			top[v]=v; 
			dfs2(v,u);
		}
	return;
}
inline void pushdown(const int k,const int l,const int r) { 
	int mid=(l+r)>>1;
	v[k<<1]+=cnt[k]*(mid-l+1),v[k<<1|1]+=cnt[k]*(r-mid);
	mx[k<<1]+=cnt[k],mx[k<<1|1]+=cnt[k];
	cnt[k<<1]+=cnt[k],cnt[k<<1|1]+=cnt[k],cnt[k]=0;
	return;
}
inline void update(const int k,const int l,const int r,const int x,const int y,const int z) {
	if(x<=l&&r<=y) {
		cnt[k]+=z,v[k]+=(r-l+1)*z,mx[k]+=z;
		return;
	}
	if(cnt[k]) pushdown(k,l,r);
	int mid=(l+r)>>1;
	if(mid>=x) update(k<<1,l,mid,x,y,z);
	if(y>mid) update(k<<1|1,mid+1,r,x,y,z);
	mx[k]=max(mx[k<<1],mx[k<<1|1]),v[k]=v[k<<1]+v[k<<1|1];
	return;
}
inline pair<int,int> query(const int k,const int l,const int r,const int x,const int y) {
	if(x<=l&&r<=y) return make_pair(v[k],mx[k]);
	if(cnt[k]) pushdown(k,l,r);
	int mid=(l+r)>>1,s=0,mx=-900000000-1;
	if(mid>=x) {
		pair<int,int> ks=query(k<<1,l,mid,x,y);
		s+=ks.first,mx=max(mx,ks.second);
	}
	if(y>mid) {
		pair<int,int> ks=query(k<<1|1,mid+1,r,x,y);
		s+=ks.first,mx=max(mx,ks.second);
	} 
	return make_pair(s,mx);
}
inline pair<int,int> ask(int u,int v) {
	int mx=-900000000-1,s=0,u1=0;
	while(top[u]!=top[v]) {
		if(dep[u]<dep[v]) swap(u,v);
		pair<int,int> k=query(1,1,n,seg[top[u]],seg[u]);
		if(top[u]==1) u1=1;
		u=father[top[u]],s+=k.first,mx=max(mx,k.second);
	}
	if(dep[u]<dep[v]) swap(u,v);
	pair<int,int> k=query(1,1,n,seg[v],seg[u]);
	if(!u1) s+=k.first,mx=max(mx,k.second);
	return make_pair(s,mx);
}
int main() {
	n=read();
	for(int i=1,u,v;i<n;i++) u=read(),v=read(),add_edge(u,v);
	for(int i=1,tmp;i<=n;i++) tmp=read(),z[i]=tmp;
	father[1]=1,top[1]=1,seg[1]=++seg[0],rev[seg[0]]=1;
	dfs1(1,1),dfs2(1,1);
	for(int i=1;i<=n;i++) update(1,1,n,seg[i],seg[i],z[i]);
	q=read();
	for(int i=1,u,v;i<=q;i++) {
		string tp;
		cin>>tp;
		u=read(),v=read();
		if(tp=="CHANGE") update(1,1,n,seg[u],seg[u],v-z[u]),z[u]=v;
		if(tp=="QMAX") printf("%d\n",ask(u,v).second);
		if(tp=="QSUM") printf("%d\n",ask(u,v).first);
	} 	
	return 0;
}

RT，树剖写炸了，可能是线段树？另外，我似乎处理不好两个点最终同时调到1的情况。HELP！