RT。

最近在学树链剖分，写了模板又来写这道(这不也是模板吗)，结果又写错了，求教。

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
ll vet[60005], head[30005], nxt[60005], num, cost[30005], numa,
    deep[30005], fa[30005], size[30005], top[30005], treemax[120005], 
    treesum[120005], pos[30005], a[30005], son[30005], n, m, R, P, x, y, z;
char q[10];
void add(ll u, ll v){
    num ++;
    vet[num] = v;
    nxt[num] = head[u];
    head[u]  = num;
}
void dfs(ll u, ll fat, ll dep){
    deep[u] = dep;
    fa[u] = fat;  
    size[u] = 1;
    ll maxson = 0, sonn = 0;
    for(int i = head[u]; i; i = nxt[i]){
        ll v = vet[i];
        if(v == fat) continue;
        dfs(v, u, dep+1);
        size[u] += size[v];
        if(size[v] > maxson){
            maxson = size[v];
            sonn = v;
        }
    }
    son[u] = sonn;
}
void DFS(ll u, ll fat, ll number){
    top[u] = number;
    numa ++; 
    a[numa] = cost[u];
    pos[u] = numa;
    if(son[u] == 0) return;
    DFS(son[u], u, number);
    for(int i = head[u]; i; i = nxt[i]){
        ll v = vet[i];
        if(v == fat || v == son[u]) continue;
        DFS(v, u, v);
    }
}
void maketree(ll p, ll l, ll r){
    if(l == r){
        treesum[p] = a[l]  ;
        treemax[p] = a[l];
        return;
    }
    ll mid = l + (r-l)/2;
    maketree(p+p, l, mid);
    maketree(p+p+1, mid+1, r);
    treesum[p] = treesum[p+p] + treesum[p+p+1];
    treemax[p] = max(treemax[p+p], treemax[p+p+1]);
}
void change(ll p, ll l, ll r, ll x, ll y){
    if(l == r && l == x){
        treesum[p] = y;
        treemax[p] = y;
        a[l] = y;
        return;
    }
    int mid = l + (r-l)/2;
    if(x <= mid) change(p+p, l, mid, x, y);
    else change(p+p+1, mid+1, r, x, y);
    treesum[p] = treesum[p+p] + treesum[p+p+1];
    treemax[p] = max(treemax[p+p], treemax[p+p+1]);
}
ll acc(ll p, ll l, ll r, ll x, ll y){
    if(l == x && r == y) return treesum[p];
    ll mid = l + (r-l)/2;
    if(x > mid) return acc(p+p+1, mid+1, r, x, y);
    else if(y <= mid) return acc(p+p, l, mid, x, y);
    else return acc(p+p, l, mid, x, mid) + acc(p+p+1, mid+1, r, mid+1, y);
}
ll acc2(ll p, ll l, ll r, ll x, ll y){
    if(l == x && r == y) return treemax[p];
    ll mid = l + (r-l)/2;
    if(x > mid) return acc2(p+p+1, mid+1, r, x, y);
    else if(y <= mid) return acc2(p+p, l, mid, x, y);
    else return max(acc2(p+p, l, mid, x, mid), acc2(p+p+1, mid+1, r, mid+1, y));
}
ll findsum(ll u, ll v){
    ll an = 0;
    while(top[u] != top[v]){
        if(deep[top[u]] < deep[top[v]]) swap(u, v);
        an = an + acc(1, 1, n, pos[top[u]], pos[u]);
        u = fa[top[u]];
    }
    if(deep[u] < deep[v]) swap(u, v);
    return (an + acc(1, 1, n, pos[v], pos[u]))  ;
}
ll findmax(ll u, ll v){
    ll an = 0;
    while(top[u] != top[v]){
        if(deep[top[u]] < deep[top[v]]) swap(u, v);
        an = max(an, acc2(1, 1, n, pos[top[u]], pos[u]))  ;
        u = fa[top[u]];
    }
    if(deep[u] < deep[v]) swap(u, v);
    return max(an, acc2(1, 1, n, pos[v], pos[u])) ;
}
int main(){
    scanf("%lld", &n);
    for(int i = 1; i < n; i++){
        scanf("%lld%lld", &x, &y);
        add(x, y);
        add(y, x);
    }
    for(int i = 1; i <= n; i++)
        scanf("%lld", &cost[i]);
    R = 1;
    dfs(1, 0, 1);
    DFS(1, 0, 1);
    maketree(1, 1, n);
    scanf("%lld", &m);
    for(int i = 1; i <= m; i++){
        scanf("%s", q);
        if(q[0] == 'C'){
            scanf("%lld%lld", &x, &y);
            change(1, 1, n, x, y);
        }else if(q[0] == 'Q' && q[1] == 'S'){
            scanf("%lld%lld", &x, &y);
            printf("%lld\n", findsum(x, y));
        }else {
            scanf("%lld%lld", &x, &y);
            printf("%lld\n", findmax(x, y));
        }
    }
    return 0;
}