bzoj2631 -- LCT

包含了link、cut、update、query操作。

更新时类似线段树就可以了。

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
#define N 100010
#define M 51061
#define ll unsigned int
inline char nc(){
    static char buf[100000],*p1=buf,*p2=buf;
    if(p1==p2){
        p2=(p1=buf)+fread(buf,1,100000,stdin);
        if(p1==p2)return EOF;
    }
    return *p1++;
}
inline void Read(int& x){
    char c=nc();
    for(;c<'0'||c>'9';c=nc());
    for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=nc());
}
inline void Read(char& C){
    char c=nc();
    for(;c!='+'&&c!='*'&&c!='-'&&c!='/';c=nc());
    C=c;
}
int Len;
char S[30];
inline void Print(ll x){
    if(x==0)putchar(48);
    for(Len=0;x;x/=10)S[++Len]=x%10;
    for(;Len;)putchar(S[Len--]+48);putchar('
');
}
int i,j,k,n,m,Q,f[N],h[N],ch[N][2],x,y,z,s[N];
ll Sum[N],p1[N],p2[N],a[N];
bool b[N],r[N];
char C;
inline int Get(int x){return ch[f[x]][1]==x;}
inline void Update_rev(int x){
    if(x==0)return;
    r[x]^=1;swap(ch[x][0],ch[x][1]);
}
inline void Update_mul(int x,int y){
    Sum[x]=(Sum[x]*y)%M;a[x]=(a[x]*y)%M;p1[x]=(p1[x]*y)%M;p2[x]=(p2[x]*y)%M;
}
inline void Update_add(int x,int y){
    Sum[x]=(Sum[x]+y*s[x])%M;a[x]=(a[x]+y)%M;p2[x]=(p2[x]+y)%M;
}
inline void Pushdown(int x){
    if(r[x]){
        Update_rev(ch[x][0]);
        Update_rev(ch[x][1]);
        r[x]=0;
    }
    if(p1[x]!=1){
        Update_mul(ch[x][0],p1[x]);
        Update_mul(ch[x][1],p1[x]);
        p1[x]=1;
    }
    if(p2[x]){
        Update_add(ch[x][0],p2[x]);
        Update_add(ch[x][1],p2[x]);
        p2[x]=0;
    }
}
inline void Pushup(int x){
    Sum[x]=(Sum[ch[x][0]]+Sum[ch[x][1]]+a[x])%M;
    s[x]=s[ch[x][0]]+s[ch[x][1]]+1;
}
inline void Rotate(int x){
    int y=f[x];bool d=Get(x);
    if(b[y])b[y]=0,b[x]=1;else ch[f[y]][Get(y)]=x;
    ch[y][d]=ch[x][d^1];f[ch[y][d]]=y;
    ch[x][d^1]=y;f[x]=f[y];f[y]=x;
    Pushup(y);
}
inline void P(int x){if(!b[x])P(f[x]);Pushdown(x);}
inline void Splay(int x){
    for(P(x);!b[x];Rotate(x))
    if(!b[f[x]])Rotate(Get(x)==Get(f[x])?f[x]:x);
    Pushup(x);
}
inline void Access(int x){
    int y=0;
    while(x){
        Splay(x);
        b[ch[x][1]]=1;ch[x][1]=y;b[y]=0;
        Pushup(y=x);x=f[x];
    }
}
inline void mr(int x){Access(x);Splay(x);Update_rev(x);}
inline void Link(int x,int y){mr(x);f[x]=y;}
inline void Update_Add(int x,int y,int z){
    mr(x);Access(y);Splay(y);
    Update_add(y,z);
}
inline void Update_Mul(int x,int y,int z){
    mr(x);Access(y);Splay(y);
    Update_mul(y,z);
}
inline void Del(int x,int y){
    mr(x);Access(y);Splay(y);
    f[x]=ch[y][0]=0;b[x]=1;Pushup(y);
}
inline ll Query(int x,int y){
    mr(x);Access(y);Splay(y);
    return Sum[y];
}
int main()
{
    Read(n);Read(Q);
    for(i=1;i<=n;i++)a[i]=b[i]=Sum[i]=s[i]=p1[i]=1;
    for(i=1;i<n;i++)Read(x),Read(y),Link(x,y);
    while(Q--){
        Read(C);
        if(C=='+')Read(x),Read(y),Read(z),Update_Add(x,y,z);else
        if(C=='-')Read(x),Read(y),Del(x,y),Read(x),Read(y),Link(x,y);else
        if(C=='*')Read(x),Read(y),Read(z),Update_Mul(x,y,z);else Read(x),Read(y),Print(Query(x,y));
    }
    return 0;
}