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的余数。

Input

　　第一行两个整数n，q

接下来n-1行每行两个正整数u，v。描写叙述这棵树

接下来q行，每行描写叙述一个操作

Output

　　对于每一个/相应的答案输出一行

Sample Input

3 2

1 2

2 3

• 1 3 4

/ 1 1

Sample Output

4

HINT

数据规模和约定

10%的数据保证，1<=n。q<=2000

另外15%的数据保证，1<=n。q<=5*10^4。没有-操作。而且初始树为一条链

另外35%的数据保证。1<=n，q<=5*10^4，没有-操作

100%的数据保证，1<=n，q<=10^5，0<=c<=10^4

Source

显然直接LCT即可了…给加和乘打下标记就能够.

记得计算时候要split而不是cut…不要删边!!!

我傻逼把加和乘的标记写成了bool…WA了4发233

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define MAXN 100010

#define LL unsigned int

#define P 51061

using namespace std;

char ch[3];

int u,v,w;

int n,m;

int sta[MAXN],top;

struct splay

{

    int fa,ch[2],size;

    bool rev;

    LL sum,w,time,plus;

}tree[MAXN];

void in(int &x)

{

    char ch=getchar();int flag=1;x=0;

    while (!(ch>='0'&&ch<='9')) flag=ch=='-'?-1:1,ch=getchar();

    while (ch>='0'&&ch<='9')    x=x*10+ch-'0',ch=getchar();x*=flag;

}

bool is_root(int x)

{

    return tree[tree[x].fa].ch[0]!=x&&tree[tree[x].fa].ch[1]!=x;

}

void push_up(int x)

{

    tree[x].sum=(tree[tree[x].ch[0]].sum+tree[tree[x].ch[1]].sum+tree[x].w)%P;

    tree[x].size=(tree[tree[x].ch[0]].size+tree[tree[x].ch[1]].size+1)%P;

}

void calc(int x,int tim,int plu)

{

    if (!x) return;

    tree[x].w=(tree[x].w*tim+plu)%P;

    tree[x].sum=(tree[x].sum*tim+plu*tree[x].size)%P;

    tree[x].plus=(tree[x].plus*tim+plu)%P;

    tree[x].time=(tree[x].time*tim)%P;

}

void push_down(int x)

{

    if (tree[x].rev)

    {

        tree[x].rev^=1;tree[tree[x].ch[0]].rev^=1;tree[tree[x].ch[1]].rev^=1;

        swap(tree[x].ch[0],tree[x].ch[1]);

    }

    if (tree[x].time!=1||tree[x].plus!=0)   calc(tree[x].ch[0],tree[x].time,tree[x].plus),calc(tree[x].ch[1],tree[x].time,tree[x].plus);

    tree[x].time=1;tree[x].plus=0;

}

void rot(int x)

{

    int y=tree[x].fa,z=tree[y].fa,l,r;

    l=(tree[y].ch[1]==x);r=l^1;

    if (!is_root(y))    tree[z].ch[tree[z].ch[1]==y]=x;

    tree[tree[x].ch[r]].fa=y;tree[y].fa=x;tree[x].fa=z;

    tree[y].ch[l]=tree[x].ch[r];tree[x].ch[r]=y;

    push_up(y);push_up(x);

}

void Splay(int x)

{

    sta[++top]=x;

    for (int i=x;!is_root(i);i=tree[i].fa)  sta[++top]=tree[i].fa;

    while (top) push_down(sta[top--]);

    while (!is_root(x))

    {

        int y=tree[x].fa,z=tree[y].fa;

        if (!is_root(y))

        {

            if (tree[y].ch[0]==x^tree[z].ch[0]==y)  rot(x);

            else    rot(y);

        }

        rot(x);

    }

}

void access(int x)

{

    for (int i=0;x;i=x,x=tree[x].fa)    Splay(x),tree[x].ch[1]=i,push_up(x);

}

void make_root(int x)

{

    access(x);Splay(x);tree[x].rev^=1;

}

void link(int x,int y)

{

    make_root(x);tree[x].fa=y;

}

void split(int x,int y)//为了获得信息要拆子树可是不能删边!!!

{

    make_root(y);access(x);Splay(x);

}

void cut(int x,int y)

{

    make_root(x);access(y);Splay(y);tree[y].ch[0]=tree[x].fa=0;

}

int main()

{

    in(n);in(m);

    for (int i=1;i<=n;i++)  tree[i].w=tree[i].sum=tree[i].size=tree[i].time=1;

    for (int i=1;i<n;i++)

    {

        in(u);in(v);

        link(u,v);

    }

    while (m--)

    {

        scanf("%s",ch);in(u);in(v);

        if (ch[0]=='+') in(w),split(u,v),calc(u,1,w);

        if (ch[0]=='-') cut(u,v),in(u),in(v),link(u,v);

        if (ch[0]=='*') in(w),split(u,v),calc(u,w,0);

        if (ch[0]=='/') split(u,v),printf("%u\n",tree[u].sum);

    }

}