rt,用的是重链剖分，代码如下

#include <bits/stdc++.h>

using namespace std;
const int maxn = 3e4 + 5;
#define ls u << 1
#define rs u << 1 | 1
struct edge {
    int from, to, next, val;
} g[maxn << 1];
struct node {
    int l, r, mx, sum;
} t[maxn << 2];
int head[maxn], k, tot, a[maxn], b[maxn], f[maxn], fa[maxn], dfn[maxn], son[maxn], dep[maxn], siz[maxn];
void add(int u, int v) {
    g[++k].to = v;
    g[k].from = u;
    g[k].next = head[u];
    head[u] = k;
}

void push_up(int u) {
    t[u].sum = t[ls].sum + t[rs].sum;
    t[u].mx = max(t[ls].mx, t[rs].mx);
}
void build(int u, int l, int r) {
    t[u] = {l, r, -1000000000,0};
    if (l == r) {
        t[u].sum = b[l];
        t[u].mx = b[l];
        return;
    }
    int mid= (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    push_up(u);
}
void modify(int u, int x, int v) {
    if (t[u].l == x &&t[u].r == x) {
        t[u].sum = v;
        t[u].mx = v;
        return;
    } else {
        int mid = (t[u].l + t[u].r) >> 1;
        if (x <= mid) {
            modify(ls, x, v);
        } else {
            modify(rs, x, v);
        }
        push_up(u);
    }
}
int query (int u, int l, int r, int opt) {
    if (l <= t[u].l && t[u].r <= r) {
        return (opt ? t[u].sum : t[u].mx);
    } else {
        int mid = (t[u].l + t[u].r) >> 1;
        int res = opt ? 0 : -1e9;
        if (l <= mid) {
            res = query(ls, l, r, opt);
        }
        if (r > mid) {
            int s = query(rs, l, r, opt);
            res = opt ? res + s : max(res, s);
        }
        return res;
    }
}

int ask (int x, int y, int opt) {
    int ans = opt ? 0 : -1e9;
    if (x == y) {
        return query(1, dfn[x], dfn[x], 0);
    }
    while (f[x] != f[y]) {
        if (dep[f[x]] < dep[f[y]]) {
            swap(x, y);
        }
        int res = query(1, dfn[f[x]], dfn[x], opt);
        ans = opt ? ans + res : max(ans, res);
        x = fa[f[x]];
    }
    if (dep[x] > dep[y]) {
        swap(x, y);
    }
    if (x != y) {
        int res = query(1, dfn[x], dfn[y], opt);
        ans = opt ? ans + res : max(ans, res);
    }
    return ans;
}
void dfs1(int u, int depth, int father) {
    siz[u] = 1;
    dep[u] = depth;
    fa[u] = father;
    for (int i = head[u]; i; i = g[i].next) {
        int v = g[i].to;
        if (v == fa[u]) {
            continue;
        }
        dfs1(v, depth + 1, u);
        siz[u] += siz[v];
        if (siz[v] > siz[son[u]]) {
            son[u] = v;
        }
    }
}

void dfs2(int u, int s) {
    dfn[u] = ++tot;
    b[tot] = a[u];
    f[u] = s;
    if (!son[u]) {
        return;
    }
    dfs2(son[u], s);
    for (int i = head[u]; i; i = g[i].next) {
        int v = g[i].to;
        if (v != son[u] && v != fa[u]) {
            dfs2(v, v);
        }
    }
}

void solve() {
    int n;
    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];
    }
    dfs1(1, 1, 0);
    dfs2(1, 1);
    build(1, 1, n);
    int q;
    cin >> q;
    while (q--) {
        string opt;
        int u, v;
        cin >> opt >> u >> v;
        if (opt == "CHANGE") {
            modify(1, dfn[u], v);
        } else if (opt == "QMAX") {
            if (u > v) {
                swap(u, v);
            }
            cout << ask(u, v, 0) << '\n';
        } else {
            if (u > v) {
                swap(u, v);
            }
            cout << ask(u, v, 1) << '\n';
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();

    return 0;
}