求调

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline ll max(ll a,ll b){
	return a>b?a:b;
}
inline ll min(ll a,ll b){
	return a>b?b:a;
}
const int N=3e4+10;
int n,q;
int u,v;
struct segment_tree{
	ll s[N<<2],mx[N<<2];
	ll data[N];
	int ls(int p){return p<<1;}
	int rs(int p){return p<<1|1;}
	void push_up(int p){
		s[p]=s[ls(p)]+s[rs(p)];
		mx[p]=max(mx[ls(p)],mx[rs(p)]);
	}
	void build(int p,int pl,int pr){
		if(pl==pr){
			s[p]=data[pl];
			mx[p]=data[pl];
			return ;
		}
		int mid=pl+(pr-pl>>1);
		build(ls(p),pl,mid);
		build(rs(p),mid+1,pr);
		push_up(p);
	}
	void update(int p,int pl,int pr,int L,int R,ll k){
		if(L<=pl&&pr<=R){
			s[p]+=k;
			mx[p]+=k;
			return ;
		}
		int mid=pl+(pr-pl>>1);
		if(L<=mid)update(ls(p),pl,mid,L,R,k);
		if(mid+1<=R)update(rs(p),mid+1,pr,L,R,k);
		push_up(p);
	}
	pair<ll,ll> query(int p,int pl,int pr,int L,int R){
		if(L<=pl&&pr<=R){
			return {mx[p],s[p]};
		}
		int mid=pl+(pr-pl>>1);
		pair<ll,ll>ret={-1e18,0};
		pair<ll,ll>tmp;
		if(L<=mid){
			tmp=query(ls(p),pl,mid,L,R);
			ret.second+=tmp.second;
			ret.first=max(ret.first,tmp.first);
		}
		if(mid+1<=R){
			tmp=query(rs(p),mid+1,pr,L,R);
			ret.second+=tmp.second;
			ret.first=max(ret.first,tmp.first);
		}
		return ret;
	}
};
struct cut_tree{
	vector<int>G[N];
	int fa[N],dep[N],siz[N],son[N],top[N],dfn[N],rank[N];
	int cnt;
	void init(int root){
		cnt=0;
		dep[root]=1;
	}
	void dfs1(int u){
		son[u]=-1;
		siz[u]=1;
		for(auto v:G[u]){
			if(dep[v])continue;
			dep[v]=dep[u]+1;
			fa[v]=u;
			dfs1(v);
			siz[u]+=siz[v];
			if(son[u]==-1||siz[v]>siz[son[u]])son[u]=v;
		}
	}
	void dfs2(int u,int root){
		top[u]=root;
		dfn[u]=++cnt;
		rank[cnt]=u;
		if(son[u]==-1)return ;
		dfs2(son[u],root);
		for(auto v:G[u])
			if(v!=son[u]&&v!=fa[u])
				dfs2(v,v);
	}
	pair<ll,ll> query(int x,int y,segment_tree& tree){
		pair<ll,ll>ret={-1e18,0};
		int fx=top[x],fy=top[y];
		while(fx!=fy){
			if(dep[fx]>=dep[fy]){
				ret.first=max(ret.first,tree.query(1,1,n,dfn[fx],dfn[x]).first);
				ret.second+=tree.query(1,1,n,dfn[fx],dfn[x]).second;
				x=fa[fx];
			}
			else{
				ret.first=max(ret.first,tree.query(1,1,n,dfn[fy],dfn[y]).first);
				ret.second+=tree.query(1,1,n,dfn[fx],dfn[x]).second;
				y=fa[fy];
			}
			fx=top[x];
			fy=top[y];
		}
		if(dfn[x]<dfn[y]){
			ret.first=max(ret.first,tree.query(1,1,n,dfn[x],dfn[y]).first);
			ret.second+=tree.query(1,1,n,dfn[x],dfn[y]).second; 
		}
		else{
			ret.first=max(ret.first,tree.query(1,1,n,dfn[x],dfn[y]).first);
			ret.second+=tree.query(1,1,n,dfn[y],dfn[x]).second; 
		}
		return ret;
	}
};
segment_tree st;
cut_tree cut;
ll w[N];
string s;
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		cut.G[u].push_back(v);
		cut.G[v].push_back(u);
	}
	for(int i=1;i<=n;i++)scanf("%lld",&w[i]);
	cut.init(1);
	cut.dfs1(1);
	cut.dfs2(1,1);
	for(int i=1;i<=n;i++)st.data[i]=w[cut.rank[i]];
	st.build(1,1,n);
	scanf("%d",&q);
	while(q--){
		cin>>s;
		scanf("%d%d",&u,&v);
		if(s=="CHANGE"){
			st.update(1,1,n,cut.dfn[u],cut.dfn[u],v);
		}
		else{
			pair<ll,ll>ans=cut.query(u,v,st);
			if(s=="QMAX"){
				printf("%lld\n",ans.first);
			}
			else{
				printf("%lld\n",ans.second);
			}
		}
	}
	return 0;
}