PLCT检查是什么洛谷P1501 [国家集训队]Tree II（打标记lct）

#include<map>
#include<set>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 100010
#define mod 51061
#define lson ch[x][0]
#define rson ch[x][1]
#define int long long
using namespace std;

int tag1[N],tag2[N],tag3[N],sum[N],sz[N],f[N],ch[N][2],w[N];

int not_root(int now)
{
    int x=f[now];
    return lson==now||rson==now;
}

int push_up(int x)
{
    sum[x]=(sum[lson]+sum[rson]+w[x])%mod;
    sz[x]=sz[lson]+sz[rson]+1;
}

int rev(int x)
{
    swap(lson,rson);
    tag1[x]^=1;
}

int add(int x,int cost)
{
    sum[x]+=cost*sz[x];
    sum[x]%=mod;
    w[x]+=cost;
    w[x]%=mod;
    tag2[x]+=cost;
    tag2[x]%=mod;
}

int mul(int x,int cost)
{
    sum[x]*=cost;
    sum[x]%=mod;
    w[x]*=cost;
    w[x]%=mod;
    tag3[x]*=cost;
    tag3[x]%=mod;
    tag2[x]*=cost;
    tag2[x]%=mod;
}

int push_down(int x)

    if(tag2[x])
    {
        add(lson,tag2[x]);
        add(rson,tag2[x]);
        tag2[x]=0;
    }
    if(tag1[x])
    {
        rev(lson);
        rev(rson);
        tag1[x]=0;
    }
}

int rotate(int x)

    ch[x][!kd]=y;
    ch[y][kd]=xs;
    if(xs) f[xs]=y;
    f[y]=x;
    f[x]=z;
    push_up(y);
}

int push_all(int x)

    push_down(x);
}

int splay(int x)

        rotate(x);
    }
    push_up(x);
}

int access(int x)
{
    for(int y=0; x; y=x,x=f[x])
    {
        splay(x);
        rson=y;
        push_up(x);
    }
}

int make_root(int x)
{
    access(x);
    splay(x);
    rev(x);
}

int split(int x,int y)
{
    make_root(x);
    access(y);
    splay(y);
}

int link(int x,int y)
{
    make_root(x);
    f[x]=y;
}

int cut(int x,int y)
{
    split(x,y);
    f[x]=ch[y][0]=0;
}

char s[3];
int n,m;

signed main()
{
    scanf("%lld %lld",&n,&m);
    for(int i=1; i<=n; i++)
    {
        sum[i]=w[i]=tag3[i]=sz[i]=1;
    }
    for(int i=1; i<n; i++)
    {
        int from,to;
        scanf("%lld %lld",&from,&to);
        link(from,to);
    }
    for(int i=1; i<=m; i++)

        if(s[0]=='-')
        {
            int u1,v1,u2,v2;
            scanf("%lld %lld %lld %lld",&u1,&v1,&u2,&v2);
            cut(u1,v1);
            link(u2,v2);
        }
        if(s[0]=='+')
        {
            int x,y,cost;
            scanf("%lld %lld %lld",&x,&y,&cost);
            split(y,x);
            add(x,cost);
        }
        if(s[0]=='/')
        {
            int u,v;
            scanf("%lld %lld",&u,&v);
            split(u,v);
            printf("%lld
",sum[v]);
        }
    }
}