LCT求调

#include<bits/stdc++.h>
using namespace std;
long long n,q;
#define MAXN 500505
long long ch[MAXN][2],Multi[MAXN],s[MAXN],lz[MAXN],v[MAXN];//M:Multilazytag,S=Sum,LZ:sumlazy
bool rev[MAXN];
long long siz[MAXN],f[MAXN];
#define MOD 51061
#define ls(x) (ch[x][0])
#define rs(x) (ch[x][1])


namespace LCT{
    bool isroot(long long x){
        return ls(f[x])==x||rs(f[x])==x;
    }
    bool Get(long long x){return x==rs(f[x]);}
    void pushrev(long long x){swap(ls(x),rs(x));rev[x]^=1;}
    void pushup(long long x){s[x]=(s[ls(x)]+s[rs(x)]+v[x])%MOD;siz[x]=siz[ls(x)]+siz[rs(x)]+1;}
    void push_Multi(long long x,long long c){
        s[x]=(s[x]*c)%MOD;v[x]=(v[x]*c)%MOD;Multi[x]=(Multi[x]*c)%MOD;lz[x]=(lz[x]*c)%MOD;
    }
    void push_Add(long long x,long long c){
        s[x]=(s[x]+c*siz[x])%MOD;v[x]=(v[x]+c)%MOD;lz[x]=(lz[x]+c)%MOD;
    }
    void pushdown(long long x){
        if(Multi[x]!=1)push_Multi(ls(x),Multi[x]),push_Multi(rs(x),Multi[x]),Multi[x]=1;
        if(lz[x]!=0)push_Add(ls(x),lz[x]),push_Add(rs(x),lz[x]),lz[x]=0;
        if(rev[x]){if(ls(x))pushrev(ls(x));if(rs(x))pushrev(rs(x));rev[x]=0;}
    }
    void rotate(long long x){
        long long y=f[x],z=f[y],k=Get(x),w=ch[x][!k];
        if(isroot(y))ch[z][rs(z)==y]=x;
        ch[x][!k]=y;ch[y][k]=w;
        if(w)f[w]=y;
        f[y]=x,f[x]=z;
        pushup(y);
    }
    void Update(long long x){if(isroot(x))Update(f[x]);pushdown(x);}//爬到树根去往下传
    void splay(long long x){
        Update(x);
        while(isroot(x)){
            long long y=f[x],z=f[y];
            if(isroot(y))rotate((((ls(y)==x)^(ls(z)==y))?x:y));
            rotate(x);
        }
        pushup(x);
    }
    void access(long long x){
        for(long long y=0;x;x=f[y=x]){splay(x);rs(x)=y;pushup(x);}
    }
    void makeroot(long long x){access(x);splay(x);pushrev(x);}
    long long findroot(long long x){
        access(x);splay(x);
        while (ls(x)){pushdown(x);x=ls(x);}
        splay(x);
        return x;
    }
    void split(long long x,long long y){makeroot(x);access(y);splay(y);}
    void link(long long x,long long y){makeroot(x);if(findroot(y)!=x)f[x]=y;}
    void cut(long long x,long long y){
        makeroot(x);access(y);splay(y);ls(x)=f[x]=0;
    }
}


int main(){
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    scanf("%lld%lld",&n,&q);
    for(long long i=1;i<=n;++i)v[i]=siz[i]=Multi[i]=1;
    for(long long i=1;i<n;++i ){long long u,v;scanf("%lld%lld",&u,&v);LCT::link(u,v);}
    while(q--){
        string S;cin>>S;
        if(S=="+"){long long u,v,c;scanf("%lld%lld%lld",&u,&v,&c);LCT::split(u,v);LCT::push_Add(u,c);}
        else if(S=="-"){long long u,v,U,V;scanf("%lld%lld%lld%lld",&u,&v,&U,&V);LCT::cut(u,v);LCT::link(U,V);}
        else if(S=="*"){long long u,v,c;scanf("%lld%lld%lld",&u,&v,&c);LCT::split(u,v);LCT::push_Multi(u,c);}
        else {long long u,v;scanf("%lld%lld",&u,&v);LCT::split(u,v);printf("%lld\n",s[u]);
        }
        
    }
    return 0;
}