数据结构（动态树）：[国家集训队2012]tree(伍一鸣)

【问题描述】

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

【输入格式】

第一行两个整数n，q
接下来n-1行每行两个正整数u，v，描述这棵树
接下来q行，每行描述一个操作

【输出格式】

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

【样例输入】

3 2
1 2
2 3
* 1 3 4
/ 1 1

【样例输出】

【数据规模和约定】

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

　　犯了几个错误：

　　　　1.mul标记下传时没有让mul*k。

　　　　2.数组开小了。

　　　　3.递归栈慢！！！

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int mod=51061;
const int maxn=50010;

int fir[maxn],nxt[maxn*2],to[maxn*2],cnt;

void addedge(int a,int b){
    nxt[++cnt]=fir[a];
    fir[a]=cnt;
    to[cnt]=b;
}

int fa[maxn],rt[maxn];
int ch[maxn][2],key[maxn],sz[maxn];
int sum[maxn],flip[maxn],add[maxn],mul[maxn];

void DFS(int x){
    rt[x]=sz[x]=key[x]=sum[x]=mul[x]=1;
    for(int i=fir[x];i;i=nxt[i])    
        if(to[i]!=1&&!fa[to[i]]){
            fa[to[i]]=x;
            DFS(to[i]);
        }
}

void Add(int x,int d){
    if(!x)return;
    key[x]=(key[x]+d)%mod;
    add[x]=(add[x]+d)%mod;
    sum[x]=(sum[x]+sz[x]*d%mod)%mod;
}

void Mul(int x,int k){
    key[x]=(key[x]*k)%mod;
    sum[x]=(sum[x]*k)%mod;
    add[x]=(add[x]*k)%mod;
}

void Flip(int x){
    swap(ch[x][0],ch[x][1]);
    flip[x]^=1;
}

void Push_down(int x){
    if(flip[x]){
        Flip(ch[x][0]);
        Flip(ch[x][1]);
        flip[x]=0;
    }
    if(mul[x]!=1){
        Mul(ch[x][0],mul[x]);
        Mul(ch[x][1],mul[x]);
        mul[x]=1;
    }
    if(add[x]){
        Add(ch[x][0],add[x]);
        Add(ch[x][1],add[x]);
        add[x]=0;
    }
}

void Push_up(int x){
    sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
    sum[x]=(sum[ch[x][0]]+sum[ch[x][1]]+key[x])%mod;
}

void Rotate(int x){
    int y=fa[x],g=fa[y],c=ch[y][1]==x;
    ch[y][c]=ch[x][c^1];ch[x][c^1]=y;
    fa[ch[y][c]]=y;fa[y]=x;fa[x]=g;
    if(rt[y])rt[x]=1,rt[y]=0;
    else ch[g][ch[g][1]==y]=x;
    Push_up(y);
}

void P(int x){
    if(!rt[x])P(fa[x]);
    Push_down(x);
}

void Splay(int x){
    P(x);
    for(int y=fa[x];!rt[x];Rotate(x),y=fa[x])
        if(!rt[y])Rotate((ch[fa[y]][1]==y)==(ch[y][1]==x)?y:x);
    Push_up(x);    
}

void Access(int x){
    int y=0;
    while(x){
        Splay(x);
        rt[ch[x][1]]=1;
        rt[ch[x][1]=y]=0;
        Push_up(x);
        x=fa[y=x];
    }
}

void Make_RT(int x){
    Access(x);
    Splay(x);
    Flip(x);
}

void Link(int x,int y){
    Make_RT(x);
    fa[x]=y;
}

void Cut(int x,int y){
    Make_RT(x);
    Splay(y);
    fa[ch[y][0]]=fa[y];fa[y]=0;
    rt[ch[y][0]]=1;ch[y][0]=0;
    Push_up(y);
}

void Lca(int &x,int &y){
    Access(y);y=0;
    while(true){
        Splay(x);
        if(!fa[x])break;
        rt[ch[x][1]]=1;
        rt[ch[x][1]=y]=0;
        Push_up(x);
        x=fa[y=x];
    }
}

void ADD(int x,int y,int d){
    Lca(x,y);
    Add(y,d);Add(ch[x][1],d);
    key[x]=(key[x]+d)%mod;
    Push_up(x);
}

void MUL(int x,int y,int k){
    Lca(x,y);
    Mul(y,k);Mul(ch[x][1],k);
    key[x]=(key[x]*k)%mod;
    Push_up(x);
}

int Query(int x,int y){
    Lca(x,y);
    int ret=(key[x]+sum[y]+sum[ch[x][1]])%mod;
    return ret;
}

int n,Q;
char op[5];
int main(){
#ifndef ONLINE_JUDGE
    freopen("nt2012_wym_tree.in","r",stdin);
    freopen("nt2012_wym_tree.out","w",stdout);
#endif
    scanf("%d%d",&n,&Q);
    for(int i=1,a,b;i<n;i++){
        scanf("%d%d",&a,&b);
        addedge(a,b);
        addedge(b,a);
    }
    
    DFS(1);
    
    int x,y,c,u,v;
    while(Q--){
        scanf("%s",op);
        if(op[0]=='-'){
            scanf("%d%d",&u,&v);Cut(u,v);
            scanf("%d%d",&u,&v);Link(u,v);
        }
        else if(op[0]=='/'){
            scanf("%d%d",&x,&y);
            printf("%d
",Query(x,y));
        }
        else{
            scanf("%d%d%d",&x,&y,&c);
            if(op[0]=='+')
                ADD(x,y,c);
            else
                MUL(x,y,c);    
        }
    }
    return 0;    
}

爆int！！！！！