记录编号	274366	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]tree(伍一鸣)	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	18.152 s
提交时间	2016-06-28 12:25:08	内存使用	7.94 MiB

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

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;
}

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

int st[maxn],top;
void DFS(){
	st[++top]=1;
	while(top){
		int x=st[top--];
		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;
				st[++top]=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;
	mul[x]=(mul[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);
	return (key[x]+sum[y]+sum[ch[x][1]])%mod;
}

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();
	
	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\n",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;	
}