记录编号	391185	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]tree(伍一鸣)	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	8.273 s
提交时间	2017-04-05 13:45:14	内存使用	9.07 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=2e5+10,p=51061;
int n,q,w[N],next[N],head[N];
void add_edge(int f,int t){
	static int cnt=0;
	w[++cnt]=t;
	next[cnt]=head[f];
	head[f]=cnt;
}
int fa[N],son[N][2],v[N],size[N],sum[N],add[N],mul[N];
bool root[N],rev[N];
void dfs(int x){
	root[x]=1;size[x]=v[x]=sum[x]=1;
	for (int i=head[x];i;i=next[i])
		if (!fa[w[i]]) fa[w[i]]=x,dfs(w[i]);
}
//规定：先传乘法，再传加法 
#define lc son[x][0]
#define rc son[x][1]
void update(int x){
	size[x]=size[lc]+size[rc]+1;
	sum[x]=(sum[lc]+sum[rc]+v[x])%p;
}
void flip(int x){
	swap(lc,rc);rev[x]^=1;
}
void modify(int x,int a,int b){
	v[x]=((ll)v[x]*a+b)%p;
	sum[x]=((ll)sum[x]*a+(ll)size[x]*b)%p;
	add[x]=((ll)add[x]*a+b)%p;
	mul[x]=((ll)mul[x]*a)%p;
}
void pushdown(int x){
	if (!x) return;
	if (rev[x]){
		if (lc) flip(lc);
		if (rc) flip(rc);
		rev[x]=0;
	}
	if (add[x]||mul[x]!=1){
		if (lc) modify(lc,mul[x],add[x]);
		if (rc) modify(rc,mul[x],add[x]);
		add[x]=0;mul[x]=1;
	}
}
void rot(int x){
	int y=fa[x],z=fa[y];
	bool b=(x==son[y][1]);
	fa[son[y][b]=son[x][!b]]=y;
	fa[son[x][!b]=y]=x;
	fa[x]=z;
	if (y==son[z][0]) son[z][0]=x;else
	if (y==son[z][1]) son[z][1]=x;
	root[x]=root[y];root[y]=0;
	update(y);update(x);
}
void splay(int x){
	pushdown(x);
	for (;!root[x];rot(x)){
		int y=fa[x],z=fa[y];
		pushdown(z);pushdown(y);pushdown(x);
		if (root[y]) continue;
		rot((x==son[y][0])==(y==son[z][0])?y:x);
	}
}
void access(int x){
	splay(x);
	root[rc]=1;rc=0;
	update(x);
	while (fa[x]){
		int y=fa[x];
		splay(y);
		root[son[y][1]]=1;
		root[son[y][1]=x]=0;
		update(y);
		splay(x);
	}
}
void makeroot(int x){
	access(x);
	flip(x);
}
int main()
{
	freopen("nt2012_wym_tree.in","r",stdin);
	freopen("nt2012_wym_tree.out","w",stdout);
	scanf("%d%d",&n,&q);
	for (int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add_edge(x,y);
		add_edge(y,x);
	}
	fa[1]=1;dfs(1);fa[1]=0;
	int u,v,u1,v1,c;
	while (q--){
		char ch=0;
		while (ch!='+'&&ch!='-'&&ch!='*'&&ch!='/') ch=getchar();
		scanf("%d%d",&u,&v);
		makeroot(u);
		access(v);
		if (ch=='+') scanf("%d",&c),modify(v,1,c);
		if (ch=='-'){
			scanf("%d%d",&u1,&v1);
			fa[u]=son[v][0]=0;
			root[u]=1;
			update(v);
			makeroot(u1);
			fa[u1]=v1;
		}
		if (ch=='*') scanf("%d",&c),modify(v,c,0);
		if (ch=='/') printf("%d\n",sum[v]);
	}
	return 0;
}