求调

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<limits>
#include<list>
#include<map>
#include<iomanip>
#include<ios>
#include<sstream>
#include<stack>
#include<bitset>
#include<cctype>
#include<stdexcept>
#include<streambuf>
#include<utility>
#include<vector>
#include<iosfwd>
#include<cerrno>
#include<clocale>
#include<complex>
#include<cstdlib>
#include<ctime>
#include<istream>
#include<ostream>
#include<queue>
#include<set>
#include<cwchar>
#include<cwctype>
#include<complex.h>
#include<fenv.h>
#include<inttypes.h>
#include<stdbool.h>
#include<stdint.h>
#include<tgmath.h>
#include<stdlib.h>
#include<time.h>
#include<numeric>
using namespace std;
#define re register
#define itn int
#define nt int
#define retun return
#define xin cin
#define endl "\n"
typedef long long ll;//unsigned
const int maxn=1e6+5;
int n,q,root=1,dfn=0;
vector<int> G[maxn];
struct Node{
	int son,pre,siz,dep,top;
	int dfn,idx,val;
	Node(void)
	{
		son=-1,pre=-1,siz=1,dep=0,top=0;
	}
}node[maxn];
struct Tree{
	int l,r,maxx,sum,lazy;
	Tree(void)
	{
		maxx=-1e9,sum=0,lazy=0;
	}
}tree[maxn];
void dfs1(int cur,int pre)
{
	node[cur].pre=pre;
	node[cur].dep=node[pre].dep+1;
	for(auto nxt:G[cur])
	{
		if(nxt==node[cur].pre) continue;
		dfs1(nxt,cur);
		node[cur].siz+=node[nxt].siz;
		if(node[cur].son==-1) node[cur].son=nxt;
		if(node[node[cur].son].siz<node[nxt].siz)
		    node[cur].son=nxt;
	}
	return ;
}
void dfs2(int cur,int top)
{
	node[cur].dfn=++dfn;
	node[cur].top=top;
	node[dfn].idx=cur;
	if(node[cur].son==-1) return ;
	dfs2(node[cur].son,top);
	for(auto nxt:G[cur])
	{
		if(node[cur].pre==nxt) continue;
		if(node[cur].son==nxt) continue;
		dfs2(nxt,nxt);
	}
	return ;
}
//int len(int i)
//{
//	return tree[i].r-tree[i].l+1;
//}
void pushup(int i)
{
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
    tree[i].maxx=max(tree[i*2].maxx,tree[i*2+1].maxx);
    return ;
}
//void pushdown(int i)
//{
//	tree[i*2].lazy+=tree[i].lazy;
//	tree[i*2+1].lazy+=tree[i].lazy;
//	tree[i*2].sum+=tree[i].lazy*len(i*2);
//    tree[i*2+1].sum+=tree[i].lazy*len(i*2+1);
//	tree[i].lazy=0;
//}
void build(int i,int l,int r)
{
	tree[i].l=l,tree[i].r=r;
	if(l==r)
	{
		tree[i].sum=node[node[l].idx].val;
		tree[i].maxx=node[node[l].idx].val;
		return ;
	}
	int mid=l+r>>1;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
    pushup(i);
	return ;
}
void change(int i,int x,int k)
{
	if(tree[i].l==tree[i].r)
	{
		tree[i].sum=k;
		tree[i].maxx=k;
		return ;
	}
//	if(tree[i].lazy) pushdown(i);
	int mid=tree[i].l+tree[i].r>>1;
	if(x<=mid) change(i*2,x,k);
	else       change(i*2+1,x,k);
	pushup(i);
	return ;
}
int search_sum(int i,int l,int r)
{
	if(l<=tree[i].l&&tree[i].r<=r)
		return tree[i].sum;
//	if(tree[i].lazy) pushdown(i);
	int mid=tree[i].l+tree[i].r>>1,s=0;
	if(l<=mid) s+=search_sum(i*2,l,r); 
	if(mid<r)  s+=search_sum(i*2+1,l,r); 
	return s;
}
int search_max(int i,int l,int r)
{
	if(l<=tree[i].l&&tree[i].r<=r)
		return tree[i].maxx;
	int mid=tree[i].l+tree[i].r>>1,m=0;
	if(l<=mid) m=max(search_max(i*2,l,r),m); 
	if(mid<r)  m=max(search_max(i*2+1,l,r),m); 
	return m;
}
int op_max(int u,int v)
{
//	cout<<1<<endl;
	int maxx=-1e9;
	while(node[u].top!=node[v].top)
	{
		int topu=node[u].top,topv=node[v].top;
		if(node[topu].dep>node[topv].dep)
		{
			maxx=max(maxx,
			search_max(1,node[topu].dfn,node[u].dfn));
			u=node[topu].pre;
		}
		else
		{
			maxx=max(maxx,
			search_max(1,node[topv].dfn,node[v].dfn));
			v=node[topv].pre;
		}
//		cout<<maxx<<" ";
	}
	if(node[u].dep>node[v].dep)
	    maxx=max(maxx,
		search_max(1,node[v].dfn,node[u].dfn));
	else
    	maxx=max(maxx,
		search_max(1,node[u].dfn,node[v].dfn));
//	cout<<maxx<<endl;
    return maxx;
}
int op_sum(int u,int v)
{
	int sum=0;
	while(node[u].top!=node[v].top)
	{
		int topu=node[u].top,topv=node[v].top;
		if(node[topu].dep>node[topv].dep)
		{
			sum+=search_sum(1,node[topu].dfn,node[u].dfn);
			u=node[topu].pre;
		}
		else
		{
			sum+=search_sum(1,node[topv].dfn,node[v].dfn);
			v=node[topv].pre;
		}
	}
	if(node[u].dep>node[v].dep)
	    sum+=search_sum(1,node[v].dfn,node[u].dfn);
	else
    	sum+=search_sum(1,node[u].dfn,node[v].dfn);
    return sum;
}
int main()
{
    std::ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=2;i<=n;++i)
	{
		int u,v;
		cin>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
//	cout<<1<<endl;
	for(int i=1;i<=n;++i)
	    cin>>node[i].val;
	dfs1(root,root),dfs2(root,root);
	build(1,1,n);
//	cout<<1<<endl;
	cin>>q;
	while(q--)
	{
		string s;
		int x,y;
		cin>>s>>x>>y;
//		cout<<1<<endl;
		if(s[0]=='Q')
		    if(s[1]=='M') cout<<op_max(x,y)<<endl;
		    else		  cout<<op_sum(x,y)<<endl;
		else
		    change(1,node[x].dfn,y);
	}
	return 0;
}