AC on #5 #6 #9。

#include<bits/stdc++.h>
using namespace std;
const int N = 3e4+5;
const int INF = 1e9+7;
int n,q;
int a[N];
int f[N],sz[N],hs[N],dep[N];
int dfn[N],top[N],tot = 0;
vector<int> e[N];
string opt;
struct node{
	int sum,maxn;
}tree[N<<2];
void dfs1(int u,int fa){
	dep[u] = dep[fa] + 1;
	sz[u] = 1;
	f[u] = fa;
	for(auto v:e[u]){
		if(v == fa){
			continue;
		}
		dfs1(v,u);
		sz[u] += sz[v];
		if(sz[v] > sz[hs[u]]){
			hs[u] = v;
		}
	}
}
void dfs2(int u,int t){
	dfn[u] = ++tot;
	top[u] = t;
	if(!hs[u]){
		return;
	}
	dfs2(hs[u],t);
	for(auto v:e[u]){
		if(v == f[u] || v == hs[u]){
			continue;
		}
		dfs2(v,v);
	}
}
void update(int p){
	tree[p].maxn = max(tree[p<<1].maxn,tree[p<<1|1].maxn);
	tree[p].sum = tree[p<<1].sum + tree[p<<1|1].sum;
}
void build(int p,int l,int r){
	if(l == r){
		tree[p].maxn = tree[p].sum = a[dfn[l]];
		return;
	}
	int mid = (l+r) >> 1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	update(p);
}
void change(int p,int l,int r,int x,int c){
	if(l == r){
		tree[p].maxn = c;
		tree[p].sum = c;
		return;
	}
	int mid = (l+r) >> 1;
	if(x <= mid){
		change(p<<1,l,mid,x,c);
	}else{
		change(p<<1|1,mid+1,r,x,c);
	}
	update(p);
}
int query_max(int p,int l,int r,int ll,int rr){
	if(l == ll && r == rr){
		return tree[p].maxn;
	}
	int mid = (l+r) >> 1;
	if(rr <= mid){
		return query_max(p<<1,l,mid,ll,rr);
	}else if(ll > mid){
		return query_max(p<<1|1,mid+1,r,ll,rr);
	}else{
		return max(query_max(p<<1,l,mid,ll,mid),query_max(p<<1|1,mid+1,r,mid+1,rr));
	}
}
int query_sum(int p,int l,int r,int ll,int rr){
	if(l == ll && r == rr){
		return tree[p].sum;
	}
	int mid = (l+r) >> 1;
	if(rr <= mid){
		return query_sum(p<<1,l,mid,ll,rr);
	}else if(ll > mid){
		return query_sum(p<<1|1,mid+1,r,ll,rr);
	}else{
		return query_sum(p<<1,l,mid,ll,mid) + query_sum(p<<1|1,mid+1,r,mid+1,rr);
	}
}
int main(){
	for(int i=0;i<(N<<2);i++){
		tree[i].maxn = -INF;
	}
	scanf("%d",&n);
	for(int i=1;i<=n-1;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs1(1,0);
	dfs2(1,1);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	build(1,1,n);
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		int x,y;
		cin>>opt;
		scanf("%d%d",&x,&y);
		if(opt == "CHANGE"){
			change(1,1,n,dfn[x],y);
		}else if(opt == "QMAX"){
			int res = -INF;
			while(top[x] != top[y]){
				if(dep[top[x]] < dep[top[y]]){
					swap(x,y);
				}
				res = max(res,query_max(1,1,n,dfn[top[x]],dfn[x]));
				x = f[top[x]];
			}
			if(dfn[x] > dfn[y]){
				swap(x,y);
			}
			res = max(res,query_max(1,1,n,dfn[x],dfn[y]));
			printf("%d\n",res);
		}else{
			int res = 0;
			while(top[x] != top[y]){
				if(dep[top[x]] < dep[top[y]]){
					swap(x,y);
				}
				res += query_sum(1,1,n,dfn[top[x]],dfn[x]);
				x = f[top[x]];
			}
			if(dfn[x] > dfn[y]){
				swap(x,y);
			}
			res += query_sum(1,1,n,dfn[x],dfn[y]);
			printf("%d\n",res);
		}
	}
}