rt，树剖板子AC on #5#6#9，能帮看一下吗？玄2关

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=3e4+10;
int n,q,u,v,val[maxn],dep[maxn],son[maxn],top[maxn],s[maxn],rnk[maxn],dfn[maxn],fa[maxn],tot;
vector<int>g[maxn];
string opt;
struct tree{
    int l,r,sum,val;
}tr[maxn<<2];
void dfs1(int x,int fath){
    dep[x]=dep[fath]+1,s[x]=1,fa[x]=fath;
    for(int i=0;i<g[x].size();i++){
        int to=g[x][i];
        if(to==fath)
            continue;
        dfs1(to,x);
        s[x]+=s[to];
        if(!son[x]||s[son[x]]<s[to])
            son[x]=to;
    }
}
void dfs2(int x,int t){
    top[x]=t,dfn[x]=++tot,rnk[tot]=x;
    if(son[x])
        dfs2(son[x],t);
    for(int i=0;i<g[x].size();i++){
        int to=g[x][i];
        if(to==son[x]||to==fa[x])
            continue;
        dfs2(to,to);
    }
}
void push_up(int p){
    tr[p].sum=tr[p<<1].sum+tr[p<<1|1].sum;
    tr[p].val=max(tr[p<<1].val,tr[p<<1|1].val);
}
void build(int p,int l,int r){
    tr[p].l=l,tr[p].r=r;
    if(l==r){
        tr[p].sum=tr[p].val=val[rnk[l]];
        return;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid),build(p<<1|1,mid+1,r);
    push_up(p);
}
void update(int p,int x,int v){
    if(tr[p].l==tr[p].r){
        tr[p].sum=tr[p].val=v;
        return;
    }
    int mid=tr[p].l+tr[p].r>>1;
    if(mid>=x)
        update(p<<1,x,v);
    else update(p<<1|1,x,v);
    push_up(p);
}
int queryval(int p,int l,int r){
    if(l<=tr[p].l&&tr[p].r<=r)
        return tr[p].val;
    int mid=tr[p].l+tr[p].r>>1,ans=INT_MIN;
    if(mid>=l)
        ans=max(ans,queryval(p<<1,l,r));
    if(mid<r)
        ans=max(ans,queryval(p<<1|1,l,r));
    return ans;
}
int querysum(int p,int l,int r){
    if(l<=tr[p].l&&tr[p].r<=r)
        return tr[p].sum;
    int mid=tr[p].l+tr[p].r>>1,ans=0;
    if(mid>=l)
        ans+=querysum(p<<1,l,r);
    if(mid<r)
        ans+=querysum(p<<1|1,l,r);
    return ans;
}
int linkerval(int u,int v){
    int ans=INT_MIN;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])
            swap(u,v);
        ans=max(ans,queryval(1,dfn[top[u]],dfn[u]));
        u=fa[top[u]];
    }
    if(dep[u]>dep[v])
        swap(u,v);
    ans=max(ans,queryval(1,min(dfn[u],dfn[v]),max(dfn[u],dfn[v])));
    return ans;
}
int linkersum(int u,int v){
    int ans=0;
    while(top[u]!=top[v]){
        if(dep[top[u]]<dep[top[v]])
            swap(u,v);
        ans+=querysum(1,dfn[top[u]],dfn[u]);
        u=fa[top[u]];
    }
    if(dep[u]>dep[v])
        swap(u,v);
    ans+=querysum(1,min(dfn[u],dfn[v]),max(dfn[u],dfn[v]));
    return ans;
}
signed main(){
    ios::sync_with_stdio(false),cin.tie(0);
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
        cin>>val[i];
    dfs1(1,0),dfs2(1,0);
    build(1,1,n);
    cin>>q;
    while(q--){
        cin>>opt>>u>>v;
        if(opt=="CHANGE")
            update(1,dfn[u],v);
        if(opt=="QSUM")
            cout<<linkersum(dfn[u],dfn[v])<<"\n";
        if(opt=="QMAX")
            cout<<linkerval(dfn[u],dfn[v])<<"\n";
    }
    return 0;
}