1 #include <bits/stdc++.h>

  2 using namespace std;

  3 const int N = 3e4 + 10;

  4 int n, m, head[N], to[N << 1], nxt[N << 1], tot;

  5 int total, fa[N], dep[N], size[N], son[N], top[N];

  6 int w[N], id[N], rev[N];

  7 int Max, Sum;

  8 struct node{

  9     int mx, sum;

 10 }t[N << 2];

 11 void add(int x, int y) {

 12     nxt[++ tot] = head[x]; head[x] = tot; to[tot] = y;

 13 }

 14 void dfs1(int u, int f) { //求dep,fa,size,son

 15     size[u] = 1;

 16     for (int i = head[u]; i; i = nxt[i]) {

 17         int v = to[i];

 18         if (v == f) continue;

 19         dep[v] = dep[u] + 1;

 20         fa[v] = u;

 21         dfs1(v, u);

 22         size[u] += size[v];

 23         if (size[v] > size[son[u]]) son[u] = v;

 24     }

 25 }

 26 void dfs2(int u, int t) { //求top,id,rev

 27     top[u] = t;

 28     id[u] = ++ total; // u对应的dfs序下标

 29     rev[total] = u;   // dfs序下标对应的u

 30     if (!son[u]) return ;

 31     dfs2(son[u], t);//先沿重儿子dfs

 32     for (int i = head[u]; i; i = nxt[i]) {

 33         int v = to[i];

 34         if (v != fa[u] && v != son[u]) dfs2(v, v);

 35     }

 36 }

 37 namespace SegmentTree {

 38     #define mid ((l + r) >> 1)

 39     #define lson k << 1, l, mid

 40     #define rson k << 1 | 1, mid + 1, r

 41     void pushup(int k) {

 42         t[k].mx = max(t[k << 1].mx, t[k << 1 | 1].mx);

 43         t[k].sum = t[k << 1].sum + t[k << 1 | 1].sum;

 44     }

 45     void build(int k, int l, int r) {

 46         if (l == r) {

 47             t[k].mx = t[k].sum = w[rev[l]];

 48             return ;

 49         }

 50         build(lson), build(rson);

 51         pushup(k);

 52     }

 53     void update(int k, int l, int r, int pos, int v) {

 54         if (l == r) {

 55             t[k].mx = t[k].sum = v;

 56             return ;

 57         }

 58         if (pos <= mid) update(lson, pos, v);

 59         else update(rson, pos, v);

 60         pushup(k);

 61     }

 62     void query(int k, int l, int r, int L, int R) {

 63         if (L <= l && R >= r) {

 64             Max = max(Max, t[k].mx);

 65             Sum += t[k].sum;

 66             return ;

 67         }

 68         if (L <= mid) query(lson, L, R);

 69         if (R > mid) query(rson, L, R);

 70     }

 71     void ask(int u, int v) {

 72         while (top[u] != top[v]) {

 73             if(dep[top[u]] < dep[top[v]]) swap(u, v);

 74             query(1, 1, total, id[top[u]], id[u]);

 75             u = fa[top[u]];

 76         }

 77         if (dep[u] > dep[v]) swap(u, v);

 78         query(1, 1, total, id[u], id[v]);

 79     }

 80 }

 81 using namespace SegmentTree;

 82 int main() {

 83     int x, y; char str[10];

 84     scanf("%d", &n);

 85     for (int i = 1; i < n; i ++) {

 86         scanf("%d %d", &x, &y);

 87         add(x, y), add(y, x);

 88     }

 89     for (int i = 1; i <= n; i ++) scanf("%d", &w[i]);

 90     dep[1] = 1;

 91     dfs1(1, 0);

 92     dfs2(1, 1);

 93     build(1, 1, total);

 94     scanf("%d", &m);

 95     for (int i = 1; i <= m; i ++) {

 96         scanf("%s", str);

 97         scanf("%d %d", &x, &y);

 98         if(str[0] == 'C') update(1, 1, total, id[x], y);

 99         else {

100             Sum = 0;

101             Max = -0x3f3f3f3f;

102             ask(x, y);

103             if (str[1] == 'M') printf("%d\n", Max);

104             else printf("%d\n", Sum);

105         }

106     }

107     return 0;

108 }