BZOJ-2631: tree

Description

一棵n个点的树，每个点的初始权值为1。对于这棵树有q个操作，每个操作为以下四种操作之一：
+ u v c：将u到v的路径上的点的权值都加上自然数c；
- u1 v1 u2 v2：将树中原有的边(u1,v1)删除，加入一条新边(u2,v2)，保证操作完之后仍然是一棵树；
* u v c：将u到v的路径上的点的权值都乘上自然数c；
/ u v：询问u到v的路径上的点的权值和，求出答案对于51061的余数。1<=n，q<=10^5，0<=c<=10^4

LCT。。。啦啦啦。由于中间有步骤没有*1ll光荣WA+2。感觉LCT一天可学的样子。不就是加了几个标记么，splay的锅。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod=51061;
struct node
{
    node *fa,*c[2];
    int w,tur,che,ad,siz,sum;
    node(int x);
    void reverse();
    void add(int x);
    void chen(int x);
    void pushup();
    void pushdown();
}*null=new node(0),*t[101000];
node::node(int x)
{
    fa=c[0]=c[1]=null;
    sum=w=x; ad=tur=0; che=1;
    siz=null?1:0;
}
void node::reverse()
{
    if(this==null) return ;
    swap(c[0],c[1]); tur^=1;
}
void node::add(int x)
{
    if(this==null) return ;
    w=(w+x)%mod; sum+=1ll*x*siz%mod; ad=(ad+x)%mod;
}
void node::chen(int x)
{
    if(this==null) return ;
    w=1ll*w*x%mod; sum=1ll*sum*x%mod;
    che=1ll*che*x%mod; ad=1ll*ad*x%mod;
}
void node::pushup()
{
    sum=(w+c[0]->sum+c[1]->sum)%mod;
    siz=c[0]->siz+c[1]->siz+1;
}
void node::pushdown()
{
    if(tur) c[0]->reverse(),c[1]->reverse(),tur=0;
    if(che!=1) c[0]->chen(che),c[1]->chen(che),che=1;
    if(ad) c[0]->add(ad),c[1]->add(ad),ad=0;
}
int isr(node *x){return (x!=x->fa->c[0])&&(x!=x->fa->c[1]);}
void rotate(node *x)
{
    node *y=x->fa; int l=(x==y->c[1]),r=l^1;
    y->c[l]=x->c[r]; x->c[r]->fa=y;
    x->c[r]=y; x->fa=y->fa;
    if(!isr(y)) y->fa->c[(y==y->fa->c[1])]=x;
    y->fa=x; y->pushup(); x->pushup();
}
void downall(node *x)
{
    if(!isr(x)) downall(x->fa);
    x->pushdown();
}
void splay(node *x)
{
    downall(x);
    while(!isr(x))
    {
        node *y=x->fa;
        if(!isr(y)) rotate((x==y->c[0])^(y==y->fa->c[0])?x:y);
        rotate(x);
    }
}
void access(node *x)
{
    node *tmp=null;
    while(x!=null)
    {
        splay(x);
        x->c[1]=tmp; x->pushup();
        tmp=x; x=x->fa;
    }
}
void moveroot(node *x)
{
    access(x); splay(x); x->reverse();
}
void link(node *x,node *y)
{
    moveroot(x); x->fa=y;
}
void cut(node *x,node *y)
{
    moveroot(x); access(y); splay(y);
    y->c[0]=x->fa=null; y->pushup();
}
int main()
{
    int i,n,q,x,y,z;
    scanf("%d%d",&n,&q);
    for(i=1;i<=n;++i) t[i]=new node(1);
    for(i=1;i<n;++i)
    {
        scanf("%d%d",&x,&y);
        link(t[x],t[y]);
    }
    char sw; 
    while(q--)
    {
        scanf("%s",&sw);
        switch(sw)
        {
            case '+':
            {
                scanf("%d%d%d",&x,&y,&z);
                moveroot(t[x]); access(t[y]); splay(t[y]);
                t[y]->add(z); break;
            }
            case '-':
            {
                scanf("%d%d",&x,&y); cut(t[x],t[y]);
                scanf("%d%d",&x,&y); link(t[x],t[y]);
                break;
            }
            case '*':
            {
                scanf("%d%d%d",&x,&y,&z);
                moveroot(t[x]); access(t[y]); splay(t[y]);
                t[y]->chen(z); break;
            }
            case '/':
            {
                scanf("%d%d",&x,&y);
                moveroot(t[x]); access(t[y]); splay(t[y]);
                printf("%d\n",t[y]->sum%mod); break;
            }
        }
    }
    return 0;
}