样例已过

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=2e5+10;
struct line{
	int nxt,to;
};
line edge[2*N];
int head[N],tot,w[N],wt[N];
void add(int u,int v){
	tot++;
	edge[tot].to=v;
	edge[tot].nxt=head[u];
	head[u]=tot;
}
int n,q;
int dep[N],cnt=0,idt[N],son[N],fa[N],siz[N],top[N];


struct tree{
	int val,mx;
};
tree tr[4*N];
void push_up(int id){
	int id1=id*2,id2=id*2+1;
	tr[id].mx=max(tr[id1].mx,tr[id2].mx);
	tr[id].val=tr[id1].val+tr[id2].val;
}
void bui(int id,int l,int r){
	if(l==r){
		tr[id].mx=wt[l];
		tr[id].val=wt[l];
		return ;
	}
	int id1=id*2,id2=id*2+1,mid=(l+r)/2;
	bui(id1,l,mid);
	bui(id2,mid+1,r);
	push_up(id);
}
void change(int id,int l,int r,int p,int v){
	int id1=id*2,id2=id*2+1,mid=(l+r)/2;
	if(l==p and r==p){
		tr[id].mx=v;
		tr[id].val=v;
		return ;
	}
	if(p<=mid)change(id1,l,mid,p,v);
	if(p>mid)change(id2,mid+1,r,p,v);
	push_up(id);
}
int query_sum(int id,int l,int r,int x,int y){
	int id1=id*2,id2=id*2+1,mid=(l+r)/2;
	if(x<=l and r<=y)return tr[id].val;
	int ans=0;
	if(x<=mid)ans=ans+query_sum(id1,l,mid,x,y);
	if(y>mid)ans=ans+query_sum(id2,mid+1,r,x,y);
	return ans;
}
int query_mx(int id,int l,int r,int x,int y){
	int id1=id*2,id2=id*2+1,mid=(l+r)/2;
	if(x<=l and r<=y)return tr[id].mx;
	int ans=INT_MIN;
	if(x<=mid)ans=max(ans,query_mx(id1,l,mid,x,y));
	if(y>mid)ans=max(ans,query_mx(id2,mid+1,r,x,y));
	return ans;
}


int qrange_mx(int x,int y){
	int ans=INT_MIN;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ans=max(ans,query_mx(1,1,n,idt[top[x]],idt[x]));
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	ans=max(ans,query_mx(1,1,n,idt[x],idt[y]));
	return ans;
}
int qrange_sum(int x,int y){
	int ans=0;
	while(top[x]!=top[y]){
		if(dep[top[x]]<dep[top[y]])swap(x,y);
		ans=ans+query_sum(1,1,n,idt[top[x]],idt[x]);
		x=fa[top[x]];
	}
	if(dep[x]>dep[y])swap(x,y);
	ans=ans+query_sum(1,1,n,idt[x],idt[y]);
	return ans;
}
void tchange(int x,int v){
	change(1,1,n,x,v);
}
void dfs1(int x,int f,int deep){
	dep[x]=deep;
	fa[x]=f;
	siz[x]=1;
	int maxson=INT_MIN;
	for(int i=head[x];i;i=edge[i].nxt){
		int to=edge[i].to;
		if(to==f)continue;
		dfs1(to,x,deep+1);
		siz[x]+=siz[to];
		if(siz[to]>maxson){
			son[x]=to;
			maxson=siz[to];
		}
	}
}
void dfs2(int x,int topf){
	cnt++;
	idt[x]=cnt;
	wt[cnt]=w[x];
	top[x]=topf;
	if(!son[x])return ;
	dfs2(son[x],topf);
	for(int i=head[x];i;i=edge[i].nxt){
		int to=edge[i].to;
		if(to==fa[x] or to==son[x])continue;
		dfs2(to,to);
	}
}
string order[3]={"QMAX","QSUM","CHANGE"};
signed main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	for(int i=1;i<=n;i++)cin>>w[i];
	cin>>q;
	dfs1(1,0,1);
	dfs2(1,1);
	bui(1,1,n);
	for(int i=1;i<=q;i++){
		string op;
		int x,y;
		cin>>op;
		if(op==order[0]){
			cin>>x>>y;
			cout<<qrange_mx(x,y)<<"\n";
		}
		else if(op==order[1]){
			cin>>x>>y;
			cout<<qrange_sum(x,y)<<"\n";
		}
		else{
			cin>>x>>y;
			tchange(x,y);
		}
	}
	return 0;
}