树剖板子

#include<bits/stdc++.h>
#define maxn 30005
#define lc T[k].lch
#define rc T[k].rch
#define update ans=-0x7fffffff;sum=0
using namespace std;
struct node{
    int to,next;
}edi[maxn*2];
struct tree{
    int maxx,sum,l,r,lch,rch,f;
}T[maxn*4];
int head[maxn],d[maxn],v[maxn],f[maxn],top[maxn],dfn[maxn],rk[maxn],son[maxn],siz[maxn],ord,ans,sum=0,cnt;
inline void add(int u,int v)
{
    edi[++cnt].to=v;
    edi[cnt].next=head[u];
    head[u]=cnt;
    return ;
}
inline void up(int k)
{
    T[k].maxx=max(T[lc].maxx,T[rc].maxx);
    T[k].sum=T[lc].sum+T[rc].sum;
    return ;
}
inline void down(int k)
{
    T[lc].f+=T[k].f;
    T[rc].f+=T[k].f;
    T[lc].f+=T[k].f;
    T[rc].f+=T[k].f;
    T[lc].maxx+=T[k].f;
    T[rc].maxx+=T[k].f;
    T[lc].sum+=T[k].f*(T[lc].r-T[lc].l+1);
    T[rc].sum+=T[k].f*(T[rc].r-T[rc].l+1);
    T[k].f=T[k].f=0;
    return ;
}
void dfs1(int x,int dep)
{
    d[x]=dep;siz[x]=1;
    for(int i=head[x];i;i=edi[i].next)
    {
        int k=edi[i].to;
        if(d[k])continue;
        f[k]=x;
        dfs1(k,dep+1);
        siz[x]+=siz[k];
        if(!son[x]||siz[son[x]]<siz[k])son[x]=k;
    }
    return ;
}
void dfs2(int x,int num)
{
    top[x]=num;dfn[x]=++ord;rk[ord]=x;
    if(!son[x])return ;
    dfs2(son[x],num);
    for(int i=head[x];i;i=edi[i].next)
    {
        int k=edi[i].to;
        if(son[x]==k||dfn[k])continue;
        dfs2(k,k);
    }
    return ;
}
void build(int k,int l,int r)
{
    if(l==r)
    {
        T[k].l=T[k].r=l;
        T[k].maxx=T[k].sum=v[rk[l]];
        return ;
    }
    T[k].l=l;T[k].r=r;
    T[k].lch=(k<<1);T[k].rch=(k<<1)+1;
    int mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    up(k);
    return ;
}
void change(int k,int l,int r,int x)
{
    if(T[k].l>=l&&T[k].r<=r)
    {
        T[k].maxx+=x;
        T[k].sum+=x*(T[k].r-T[k].l+1);
        T[k].f+=x;
        return ;
    }
    if(T[k].f)down(k);
    int mid=(T[k].l+T[k].r)>>1;
    if(l<=mid)change(lc,l,r,x);
    if(r>mid)change(rc,l,r,x);
    up(k);
}
void qurvy_max(int k,int l,int r)
{
    if(T[k].l>=l&&T[k].r<=r)
    {
        ans=max(ans,T[k].maxx);
        return ;
    }
    if(T[k].f)down(k);
    int mid=(T[k].l+T[k].r)>>1;
    if(l<=mid)qurvy_max(lc,l,r);
    if(r>mid)qurvy_max(rc,l,r);
    up(k);
}
void qurvy_sum(int k,int l,int r)
{
    if(T[k].l>=l&&T[k].r<=r)
    {
        sum+=T[k].sum;
        return ;
    }
    if(T[k].f)down(k);
    int mid=(T[k].l+T[k].r)>>1;
    if(l<=mid)qurvy_sum(lc,l,r);
    if(r>mid)qurvy_sum(rc,l,r);
    up(k);
}
void change2(int k,int l,int x)
{
    if(T[k].l==T[k].r&&T[k].l==l)
    {
        T[k].maxx+=x;
        T[k].sum+=x*(T[k].r-T[k].l+1);
        return ;
    }
    if(T[k].f)down(k);
    int mid=(T[k].l+T[k].r)>>1;
    if(l<=mid)change2(lc,l,x);
    if(l>mid)change2(rc,l,x);
    up(k);
}
int find_max(int a,int b)
{
    update;
    int fa=top[a],fb=top[b],anss=-0x7fffffff;
    while(fa!=fb)
    {
        if(d[fa]<d[fb])
        {
            swap(fa,fb);
            swap(a,b);
        }
        update;
        qurvy_max(1,dfn[fa],dfn[a]);
        anss=max(anss,ans);
        a=f[fa];
        fa=top[a];
    }
    if(dfn[a]>dfn[b])swap(a,b);
    update;
    qurvy_max(1,dfn[a],dfn[b]);
    anss=max(anss,ans);
    return anss;
}
int find_sum(int a,int b)
{
    update;
    int fa=top[a],fb=top[b],summ=0;
    while(fa!=fb)
    {
        if(d[fa]<d[fb])
        {
            swap(fa,fb);
            swap(a,b);
        }
        update;
        qurvy_sum(1,dfn[fa],dfn[a]);
        summ+=sum;
        a=f[fa];
        fa=top[a];
    }
    if(d[a]>d[b])swap(a,b);
    update;
    qurvy_sum(1,dfn[a],dfn[b]);
    summ+=sum;
    return summ;
}
void change_un(int a,int b,int x)
{
    int fa=top[a],fb=top[b];
    while(fa!=fb)
    {
        if(d[fa]<d[fb])
        {
            swap(fa,fb);
            swap(a,b);
        }
        change(1,dfn[fa],dfn[a],x);
        a=f[fa];
        fa=top[a];
    }
    if(d[a]>d[b])swap(a,b);
    change(1,dfn[a],dfn[b],x);
    return ;
}
inline int read()
{
    int x=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
int main()
{
    int n=read(),m;
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read();
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=n;i++)v[i]=read();
    dfs1(1,1);
    dfs2(1,1);
    build(1,1,n);
    m=read();
    while(m--)
    {
        string s;
        cin>>s;
        if(s=="QMAX")
        {
            int a=read(),b=read();
            printf("%d
",find_max(a,b));
        }
        else if(s=="QSUM")
        {
            int a=read(),b=read();
            printf("%d
",find_sum(a,b));
        }
        else if(s=="CHANGE")
        {
            int a=read(),b=read();
            change2(1,dfn[a],b-v[a]);
            v[a]=b;
        }
    }
}