轻重链。

#include<bits/stdc++.h>
using namespace std;
int n,qq;
int fst[300005],cnt;
struct node
{
	int tar,nxt;
}arr[300005];
void adds(int x,int y)
{
	arr[++cnt].tar=y,arr[cnt].nxt=fst[x],fst[x]=cnt;
}
struct edge
{
	int fa,dep,size,son;
	int top,dfn,rnk;
}t[300005];
int qwq;
void dfs1(int x,int last)
{
	int maxx=-1,mxid=0;
	t[x].fa=last;t[x].dep=t[last].dep+1;t[x].size=1;
	for(int i=fst[x];i;i=arr[i].nxt)
	{
		int j=arr[i].tar;
		if(t[j].size) continue;
		dfs1(j,x);
		t[x].size+=t[j].size;
		if(t[j].size>maxx) mxid=j,maxx=t[j].size;
	}
	t[x].son=mxid;
}
void dfs2(int x,int y)
{
	t[x].dfn=++qwq;t[qwq].rnk=x;t[x].top=y;
	if(!t[x].son) return;
	dfs2(t[x].son,y);
	for(int i=fst[x];i;i=arr[i].nxt)
	{
		int j=arr[i].tar;
		if(j==t[x].fa||j==t[x].son) continue;
		dfs2(j,j);
	}
}	
int query(int x)
{
	return t[x].dfn;
}

struct segmentree
{
	int maxx,sum;
	int l,r;
}tree[820005];
int a[300005];
void build(int p,int l,int r)
{
	tree[p].l=l,tree[p].r=r;
	if(l==r)
	{
		tree[p].maxx=tree[p].sum=a[t[l].rnk];
		return;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
	tree[p].maxx=max(tree[p<<1].maxx,tree[p<<1|1].maxx);
	tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
}
void change(int p,int x,int y)
{
	if(tree[p].l>x||tree[p].r<x) return;
	if(tree[p].l==tree[p].r)
	{
		tree[p].maxx=tree[p].sum=y;
		return;
	}
	change(p<<1,x,y);
	change(p<<1|1,x,y);
	tree[p].maxx=max(tree[p<<1].maxx,tree[p<<1|1].maxx);
	tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum;
}
int query_max(int p,int l,int r)
{
	if(tree[p].l>r||tree[p].r<l) return INT_MIN;
	if(tree[p].l==tree[p].r) return tree[p].maxx;
	return max(query_max(p<<1,l,r),query_max(p<<1|1,l,r));
}
int query_sum(int p,int l,int r)
{
	if(tree[p].l>r||tree[p].r<l) return 0;
	if(tree[p].l==tree[p].r) return tree[p].sum;
	return query_sum(p<<1,l,r)+query_sum(p<<1|1,l,r);
}
int querymax(int x,int y)
{
	vector<pair<int,int> > p;
	int fx=t[x].top,fy=t[y].top;
	int res=INT_MIN;
	while(fx!=fy)
	{
		if(t[fx].dep>=t[fy].dep)
		{
			res=max(res,query_max(1,t[fx].dfn,t[x].dfn));
			x=t[fx].fa;
		}
		else
		{
			res=max(res,query_max(1,t[fy].dfn,t[y].dfn));
			y=t[fy].fa;
		}
		fx=t[x].top;
		fy=t[y].top;
	}
	if(t[x].dfn<t[y].dfn) res=max(res,query_max(1,t[x].dfn,t[y].dfn));
	else res=max(res,query_max(1,t[y].dfn,t[x].dfn));
	return res;
}
int querysum(int x,int y)
{
	int fx=t[x].top,fy=t[y].top;
	int res=0;
	while(fx!=fy)
	{
		if(t[fx].dep>=t[fy].dep)
		{
			res+=query_sum(1,t[fx].dfn,t[x].dfn);
			x=t[fx].fa;
		}
		else
		{
			res+=query_sum(1,t[fy].dfn,t[y].dfn);
			y=t[fy].fa;
		}
		fx=t[x].top;
		fy=t[y].top;
	}
	if(t[x].dfn<t[y].dfn) res+=query_sum(1,t[x].dfn,t[y].dfn);
	else res+=query_sum(1,t[y].dfn,t[x].dfn);
	return res;
}
signed main()
{
	scanf("%d",&n);
	for(int i=1;i<n;++i)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		adds(x,y);
		adds(y,x);
	}
	dfs1(1,0);dfs2(1,1);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]);
	for(int i=1;i<=2*n;++i) tree[i].maxx=INT_MIN;
	build(1,1,n);
	scanf("%d",&qq);
	while(qq--)
	{
		char a[10];
		int x,y;
		scanf("%s%d%d",&a,&x,&y);
		if(a[0]=='C') change(1,query(x),y);
		else if(a[1]=='M')
		{
			printf("%d\n",querymax(x,y));
		}
		else 
		{
			printf("%d\n",querysum(x,y));
		}
	}
	return 0;	
}