/*
HYSBZ1036
树上有1-n个结点，每个节点都有一个权值w
操作 CHANGE u t:把结点u的权值改为t
QMAX u v:询问从点u到v的路径上的节点的最大权值
QSUM u v:询问从点u到v的路径上的结点的权值和
从点u到点v路径上的结点包括u，v本身 */
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define MAXN 30010
using namespace std;
struct Edge{
int to, next;
}edge[MAXN*];
int head[MAXN], tot;
int top[MAXN];//重链顶端
int fa[MAXN];//父亲
int deep[MAXN];//深度，root=1
int num[MAXN];//子节点数
int p[MAXN];//v在线段树中的位置
int fp[MAXN];
int son[MAXN];//重儿子
int pos;
void init(){
tot = ;
memset(head, -, sizeof(head));
pos = ;
memset(son, -, sizeof(son));
}
void addedge(int u, int v){
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}
//第一次dfs求fa,deep,son,num
void dfs1(int u, int pre, int d){
deep[u] = d;
fa[u] = pre;
num[u] = ;
for(int i = head[u]; i != -; i = edge[i].next){
int v = edge[i].to;
if (v != pre){
dfs1(v, u, d+);
num[u]+=num[v];
if (son[u]==-||num[v]>num[son[u]])
son[u] = v;
}
}
}
//第二次dfs求top，p,用pos记数
void getpos(int u, int sp){//sp表示重链顶端
top[u] = sp;
p[u] = pos++;
fp[p[u]] = u;
if (son[u]==-)
return;
getpos(son[u], sp);//先把重儿子查到底
for(int i = head[u]; i != -; i = edge[i].next){
int v = edge[i].to;//轻儿子
if (v != son[u] && v != fa[u])
getpos(v, v);
}
} //线段树部分
struct Node{
int l, r;
int sum;
int Max;
}segTree[MAXN*];
inline void push_up(int i){
segTree[i].sum = segTree[i<<].sum + segTree[i<<|].sum;
segTree[i].Max = max(segTree[i<<].Max, segTree[i<<|].Max);
}
int s[MAXN];
void build(int i, int l, int r){
segTree[i].l = l;
segTree[i].r = r; if (l==r){
segTree[i].sum = segTree[i].Max = s[fp[l]];
return;
} int mid = l+r >> ;
build(i<<, l, mid);
build(i<<|, mid+, r);
push_up(i);
}
//更新线段树的第k个值为val
void update(int i, int k, int val){
if(segTree[i].l == k && segTree[i].r == k){
segTree[i].Max = segTree[i].sum = val;
return;
}
int mid = segTree[i].l + segTree[i].r >> ;
if (k <= mid)
update(i<<, k, val);
else
update(i<<|, k, val);
push_up(i);//单点更新后要重新计算Max和Sum
}
//查询[l,r]区间的最大值
int queryMax(int i, int l, int r){
if(segTree[i].l == l && segTree[i].r == r)
return segTree[i].Max;
int mid = segTree[i].l+segTree[i].r >> ;
if (r <= mid)
return queryMax(i<<, l, r);
else if (l > mid)
return queryMax(i<<|, l, r);
else
return max(queryMax(i<<, l, mid), queryMax(i<<|, mid+, r));
}
//查询[l,r]区间的和
int querySum(int i, int l, int r){
if(segTree[i].l==l && segTree[i].r == r)
return segTree[i].sum;
int mid = segTree[i].l+segTree[i].r>>;
if(r <= mid)
return querySum(i<<,l,r);
else if(l > mid)
return querySum((i<<)|,l,r);
else
return querySum(i<<, l, mid)+querySum(i<<|, mid+, r);
}
//查询u->v路径上结点的最大权值
int findMax(int u, int v){
int f1 = top[u], f2 = top[v];
int tmp = -;
while(f1!=f2){//不在同一条重链上时
if(deep[f1]<deep[f2]){
swap(u, v);
swap(f1, f2);
}
tmp = max(tmp, queryMax(, p[f1], p[u]));//把这一条链上的求出来
u = fa[f1];
f1 = top[u];
}
if (deep[u]>deep[v])
swap(u,v);
return
max(tmp, queryMax(, p[u], p[v])); }
//查询u->v路径上结点的权值
int findSum(int u, int v){
int f1 = top[u];
int f2 = top[v];
int tmp = ;
while(f1 != f2){
if (deep[f1] < deep[f2]){
swap(f1, f2);
swap(u, v);
}
tmp += querySum(, p[f1], p[u]);
u = fa[f1];
f1 = top[u];
}
if(deep[u]>deep[v])
swap(u, v);
return tmp + querySum(, p[u], p[v]);
} int main(){
int n;
int q;
char op[];
int u, v;
while(scanf("%d", &n)==){
init();
for(int i = ; i < n; i++){
scanf("%d%d", &u, &v);
addedge(u, v);
addedge(v, u);
}
for(int i = ; i <= n; i++)
scanf("%d", &s[i]); dfs1(,,);
getpos(,);
build(, , pos-); scanf("%d", &q);
while(q--){
scanf("%s%d%d", op, &u, &v);
if (op[]=='C')
update(, p[u], v);//单点修改
else if (strcmp(op, "QMAX")==)
printf("%d\n", findMax(u, v));//查询u->v路径上点权的最大值
else
printf("%d\n", findSum(u, v));//查询路径上点权的和
}
}
return ;
}