萌新求助 WA 20pts

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;
#define uLL unsigned LL
#define INF 0x3f3f3f3f
#define LL long long
#define reg register
#define rs (rt<<1|1)
#define ls (rt<<1)
#define N 30005
inline LL read(){
    LL s=0, f=1; char c=getchar();
    while(!isdigit(c)) { if(c=='-') f=-f; c=getchar(); }
    while(isdigit(c)) s=(s<<3)+(s<<1)+(c^48), c=getchar();
    return s*f;
}
struct Node {
    int mx, sm;
    Node () { mx=-INF, sm=0; }
} tr[N<<2|1];
int n, q, a[N];
int tot, t[N+N+1], nt[N+N+1], head[N];
int cnt, f[N], rk[N], son[N], siz[N], dep[N], top[N], dfn[N];
inline void Add(int x, int y) { t[++tot]=y, nt[tot]=head[x], head[x]=tot; }
inline void PushUp(int rt) { tr[rt].mx=max(tr[ls].mx, tr[rs].mx), tr[rt].sm=tr[ls].sm+tr[rs].sm; }
inline void DFS1(int r, int fa){
    f[r]=fa, dep[r]=dep[fa]+1, siz[r]=1;
    for(reg int i=head[r]; i; i=nt[i]){
        if(t[i]==fa) continue;
        DFS1(t[i], r); siz[r]+=siz[t[i]];
        if(siz[t[i]]>siz[son[r]]) son[r]=t[i];
    }
}
inline void DFS2(int r, int tp){
    top[r]=tp, dfn[r]=++cnt, rk[cnt]=r;
    if(son[r]) DFS2(son[r], tp);
    for(reg int i=head[r]; i; i=nt[i]){
        if(t[i]==f[r]) continue;
        if(t[i]==son[r]) continue;
        DFS2(t[i], t[i]);
    }
}
inline void Build(int rt, int l, int r){
    if(l==r) { tr[rt].mx=tr[rt].sm=a[rk[l]]; return ; }
    int mid=(l+r)>>1;
    Build(ls, l, mid), Build(rs, mid+1, r);
    PushUp(rt);
}
inline void Modify(int rt, int l, int r, int u, int w){
    if(l==r) { tr[rt].sm=tr[rt].mx=w; return ; }
    int mid=(l+r)>>1;
    if(u<=mid) Modify(ls, l, mid, u, w);
    else Modify(rs, mid+1, r, u, w);
    PushUp(rt);
}
inline int Query_Max(int rt, int l, int r, int u, int v){
    if(u<=l&&r<=v) return tr[rt].mx;
    int ans=-INF, mid=(l+r)>>1;
    if(u<=mid) ans=max(ans, Query_Max(ls, l, mid, u, v));
    if(v>mid) ans=max(ans, Query_Max(rs, mid+1, r, u, v));
    PushUp(rt);
    return ans;
}
inline int Query_Sum(int rt, int l, int r, int u, int v){
    if(u<=l&&r<=v) return tr[rt].sm;
    int ans=0, mid=(l+r)>>1;
    if(u<=mid) ans+=Query_Sum(ls, l, mid, u, v);
    if(v>mid) ans+=Query_Sum(rs, mid+1, r, u, v);
    PushUp(rt);
    return ans;
}
inline int Max(int x, int y){
    int mx=-INF;
    if(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x, y);
        mx=max(mx, Query_Max(1, 1, n, dfn[top[x]], dfn[x]));
        x=f[top[x]];
    }
    if(dep[x]>dep[y]) swap(x, y);
    mx=max(mx, Query_Max(1, 1, n, dfn[x], dfn[y]));
    return mx;
}
inline int Sum(int x, int y){
    int sm=0;
    if(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x, y);
        sm+=Query_Sum(1, 1, n, dfn[top[x]], dfn[x]);
        x=f[top[x]];
    }
    if(dep[x]>dep[y]) swap(x, y);
    sm+=Query_Sum(1, 1, n, dfn[x], dfn[y]);
    return sm;
}
int main(){
    n=read();
    for(reg int i=1; i<n; ++i){
        int x=read(), y=read(); 
        Add(x, y), Add(y, x);
    }
    for(reg int i=1; i<=n; ++i) a[i]=read();
    DFS1(1, 0), DFS2(1, 1), Build(1, 1, n);
    q=read();
    while(q--){
        char op[9]; scanf("%s", op);
        int x=read(), y=read(); 
        if(op[1]=='H') Modify(1, 1, n, dfn[x], y);
        if(op[1]=='M') printf("%d\n", Max(x, y));
        if(op[1]=='S') printf("%d\n", Sum(x, y));
    }
    return 0;
}