#include<bits/stdc++.h>
using namespace std;
const int MAX=1e5+5,INF=2e9+7;
int n,q,a[4*MAX];
int h[MAX],u[MAX],v[MAX],ne[MAX],tot;
int tpos[MAX],pre[MAX],cnt;
int size[MAX],wson[MAX],top[MAX],fa[MAX],d[MAX];
void add(int x,int y){
	u[++tot]=x;v[tot]=y;
	ne[tot]=h[x];h[x]=tot;
}
void dfs1(int x,int f){
	size[x]=1;
	for(int i=h[x];i!=-1;i=ne[i]){
		int y=v[i];if(y==f) continue;
		d[y]=d[y]+1;fa[y]=x;dfs1(y,x);
		size[x]+=size[y];
		if(size[y]>size[wson[x]]) wson[x]=y;
	}
}
void dfs2(int x,int tp){
	tpos[x]=++cnt;pre[cnt]=x;top[x]=tp;
	if(wson[x]) dfs2(wson[x],tp);
	for(int i=h[x];i!=-1;i=ne[i]){
		int y=v[i];
		if(y==fa[x]||y==wson[x]) continue;
		dfs2(y,y);
	}
}
int sumv[MAX<<2],maxv[MAX<<2];
void pushup(int o){
	sumv[o]=sumv[o*2]+sumv[o*2+1];
	maxv[o]=max(maxv[o*2],maxv[o*2+1]);
}
void build(int o,int l,int r){
	int mid=l+r>>1;
	if(l==r){sumv[o]=maxv[o]=a[pre[l]];return;}
	build(o*2,l,mid);build(o*2+1,mid+1,r);
	pushup(o);
}
void update(int o,int l,int r,int q,int v){
	int mid=l+r>>1;
	if(l==r){sumv[o]=maxv[o]=v;return;}
	if(q<=mid) update(o*2,l,mid,q,v);
	else update(o*2+1,mid+1,r,q,v);
	pushup(o);
}
int querysum(int o,int l,int r,int ql,int qr){
	int mid=l+r>>1,ans=0;
	if(ql<=l&&r<=qr) return sumv[o];
	if(ql<=mid) ans+=querysum(o*2,l,mid,ql,qr);
	if(qr>mid) ans+=querysum(o*2+1,mid+1,r,ql,qr);
	return ans;
} 
int querymax(int o,int l,int r,int ql,int qr){
	int mid=l+r>>1,ans=-INF;
	if(ql<=l&&r<=qr) return maxv[o];
	if(ql<=mid) ans=max(ans,querymax(o*2,l,mid,ql,qr));
	if(qr>mid) ans=max(ans,querymax(o*2+1,mid+1,r,ql,qr));
	return ans;
}
int qsum(int u,int v){
	int ans=0;
	while(top[u]!=top[v]){
		if(d[top[u]]<d[top[v]]) swap(u,v);
		ans+=querysum(1,1,n,tpos[top[u]],tpos[u]);
		u=fa[top[u]];
	}
	if(d[u]<d[v]) swap(u,v);
	ans+=querysum(1,1,n,tpos[v],tpos[u]);
	return ans;
}
int qmax(int u,int v){
	int ans=-INF;
	while(top[u]!=top[v]){
		if(d[top[u]]<d[top[v]]) swap(u,v);
		ans=max(ans,querymax(1,1,n,tpos[top[u]],tpos[u]));
		u=fa[top[u]];
	}
	if(d[u]<d[v]) swap(u,v);
	ans=max(ans,querymax(1,1,n,tpos[v],tpos[u]));
	return ans;
}
int main(){
	ios::sync_with_stdio(NULL);
	cin.tie(0);cout.tie(0);
	memset(h,-1,sizeof h);
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		add(u,v);add(v,u);
	}
	for(int i=1;i<=n;i++) cin>>a[i];
	d[1]=fa[1]=1;dfs1(1,-1);dfs2(1,1);build(1,1,n);
	cin>>q;
	while(q--){
		int x,y;
		char s[10];
		cin>>s>>x>>y;
		if(s[1]=='H') update(1,1,n,tpos[x],y);
		if(s[1]=='M') cout<<qmax(x,y)<<endl;
		if(s[1]=='S') cout<<qsum(x,y)<<endl;
	}

	return 0;
}

如题