记录编号	248006	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]tree(伍一鸣)	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	14.977 s
提交时间	2016-04-09 21:50:24	内存使用	3.56 MiB

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
const int SIZEN=100010,MOD=51061;
typedef long long LL;
int N,M;
class miku
{
public:
	int son[2],fa;
	unsigned int sum,val,add,mul,siz;
	bool rev;
	miku()
	{
		fa=son[0]=son[1]=0;
		val=sum=mul=siz=1;add=0;
	}
	#define sum(x) tr[x].sum
	#define val(x) tr[x].val
	#define mul(x) tr[x].mul
	#define siz(x) tr[x].siz
	#define rev(x) tr[x].rev
	#define add(x) tr[x].add
	#define fa(x) tr[x].fa
	#define ls(x) tr[x].son[0]
	#define rs(x) tr[x].son[1]
}tr[SIZEN];
void update(int x)
{
	if(!x) return;
	sum(x)=(sum(ls(x))+sum(rs(x))+val(x))%MOD;
	siz(x)=siz(ls(x))+siz(rs(x))+1;
}
void Node_mul(int x,int t)
{
	if(!x) return;
	sum(x)=(sum(x)*t)%MOD;
	add(x)=(add(x)*t)%MOD;
	val(x)=(val(x)*t)%MOD;
	mul(x)=(mul(x)*t)%MOD;
}
void Node_add(int x,int t)
{
	if(!x) return;
	sum(x)=(sum(x)+t*siz(x))%MOD;
	val(x)=(val(x)+t)%MOD;
	add(x)=(add(x)+t)%MOD;
}
void pushdown(int x)
{
	if(mul(x)!=1)
	{
		Node_mul(ls(x),mul(x));
		Node_mul(rs(x),mul(x));
		mul(x)=1;
	}
	if(add(x)!=0)
	{
		Node_add(ls(x),add(x));
		Node_add(rs(x),add(x));
		add(x)=0;
	}
	if(rev(x))
	{
		rev(x)^=1;
		swap(ls(x),rs(x));
		if(ls(x)) rev(ls(x))^=1;
		if(rs(x)) rev(rs(x))^=1;
	}
}
bool isroot(int x)
{
	if(fa(x)==0) return 1;
	if(ls(fa(x))==x||rs(fa(x))==x) return 0;
	return 1;
}
void rotate(int x)
{
	int y=tr[x].fa,z=tr[y].fa,l,r;
	if(tr[y].son[0]==x) l=0;
	else l=1;
	r=l^1;
	if(!isroot(y))
	{
		if(tr[z].son[0]==y) tr[z].son[0]=x;
		else tr[z].son[1]=x;
	}
	tr[tr[x].son[r]].fa=y;tr[x].fa=z;tr[y].fa=x;
	tr[y].son[l]=tr[x].son[r];tr[x].son[r]=y;
	update(y);update(x);
}
void splay(int x)
{
	pushdown(x);
	while(!isroot(x))
	{
		int y=fa(x),z=fa(y);
		pushdown(z);pushdown(y);pushdown(x);
		if(!isroot(y))
		{
			if((tr[y].son[0]==x)^(tr[z].son[0]==y)) rotate(x);
			else rotate(y);
		}
		rotate(x);
	}
}
void access(int x)
{
	int v=0;
	while(x)
	{
		splay(x);
		tr[x].son[1]=v;
		update(x);
		v=x;
		x=tr[x].fa;
	}
}
void make_root(int x)
{
	access(x);
	splay(x);
	tr[x].rev^=1;
}
void link(int u,int v)
{
	make_root(v);
	//splay(v);
	fa(v)=u;
}
void read()
{
	scanf("%d%d",&N,&M);
	int fr,to;
	for(int i=1;i<N;i++)
	{
		scanf("%d%d",&fr,&to);
		link(fr,to);
	}
}
void Path_mul(int x,int y,int t)
{
	make_root(x);
	access(y);
	splay(y);
	Node_mul(y,t);
}
void Path_add(int x,int y,int t)
{
	make_root(x);
	access(y);
	splay(y);
	Node_add(y,t);
}
void cut(int x,int y)
{
	make_root(x);
	access(y);
	splay(x);
	rs(x)=0;fa(y)=0;
	update(x);
}
int query(int x,int y)
{
	make_root(x);
	access(y);
	splay(y);
	return sum(y);
}
void work()
{
	char c;
	int fr,to,w;
	int u,v;
	for(int i=1;i<=M;i++)
	{
		while(true)
		{
			c=getchar();
			if(c!='\n'&&c!='\r') break;
		}
		//cout<<c<<endl;
		if(c=='*') 
		{
			scanf("%d%d%d",&fr,&to,&w);
			Path_mul(fr,to,w);
		}
		if(c=='/')
		{
			scanf("%d%d",&fr,&to);
			int ans=query(fr,to);
			printf("%d\n",ans);
		}
		if(c=='+')
		{
			scanf("%d%d%d",&fr,&to,&w);
			Path_add(fr,to,w);
		}
		if(c=='-')
		{
			scanf("%d%d%d%d",&fr,&to,&u,&v);
			cut(fr,to);
			link(u,v);
		}
	}
}
int main()
{
	freopen("nt2012_wym_tree.in","r",stdin);
	freopen("nt2012_wym_tree.out","w",stdout);
	tr[0].val=tr[0].sum=tr[0].add=tr[0].siz=0;
	read();
	work();
	return 0;
}