【问题描述】
一棵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的余数。
+ 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行，每行描述一个操作
接下来n-1行每行两个正整数u，v，描述这棵树
接下来q行，每行描述一个操作
【输出格式】
对于每个/对应的答案输出一行
【样例输入】
3 2
1 2
2 3
* 1 3 4
/ 1 1
1 2
2 3
* 1 3 4
/ 1 1
【样例输出】
4
【数据规模和约定】
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.递归栈慢！！！
3.
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int mod=;
const int maxn=; int fir[maxn],nxt[maxn*],to[maxn*],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][],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]=;
for(int i=fir[x];i;i=nxt[i])
if(to[i]!=&&!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][],ch[x][]);
flip[x]^=;
} void Push_down(int x){
if(flip[x]){
Flip(ch[x][]);
Flip(ch[x][]);
flip[x]=;
}
if(mul[x]!=){
Mul(ch[x][],mul[x]);
Mul(ch[x][],mul[x]);
mul[x]=;
}
if(add[x]){
Add(ch[x][],add[x]);
Add(ch[x][],add[x]);
add[x]=;
}
} void Push_up(int x){
sz[x]=sz[ch[x][]]+sz[ch[x][]]+;
sum[x]=(sum[ch[x][]]+sum[ch[x][]]+key[x])%mod;
} void Rotate(int x){
int y=fa[x],g=fa[y],c=ch[y][]==x;
ch[y][c]=ch[x][c^];ch[x][c^]=y;
fa[ch[y][c]]=y;fa[y]=x;fa[x]=g;
if(rt[y])rt[x]=,rt[y]=;
else ch[g][ch[g][]==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]][]==y)==(ch[y][]==x)?y:x);
Push_up(x);
} void Access(int x){
int y=;
while(x){
Splay(x);
rt[ch[x][]]=;
rt[ch[x][]=y]=;
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][]]=fa[y];fa[y]=;
rt[ch[y][]]=;ch[y][]=;
Push_up(y);
} void Lca(int &x,int &y){
Access(y);y=;
while(true){
Splay(x);
if(!fa[x])break;
rt[ch[x][]]=;
rt[ch[x][]=y]=;
Push_up(x);
x=fa[y=x];
}
} void ADD(int x,int y,int d){
Lca(x,y);
Add(y,d);Add(ch[x][],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][],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][]])%mod;
return ret;
} int n,Q;
char op[];
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=,a,b;i<n;i++){
scanf("%d%d",&a,&b);
addedge(a,b);
addedge(b,a);
} DFS(); int x,y,c,u,v;
while(Q--){
scanf("%s",op);
if(op[]=='-'){
scanf("%d%d",&u,&v);Cut(u,v);
scanf("%d%d",&u,&v);Link(u,v);
}
else if(op[]=='/'){
scanf("%d%d",&x,&y);
printf("%d\n",Query(x,y));
}
else{
scanf("%d%d%d",&x,&y,&c);
if(op[]=='+')
ADD(x,y,c);
else
MUL(x,y,c);
}
}
return ;
}
爆int！！！！！