[国家集训队2012]tree(伍一鸣) - /k - 223824

记录编号	223824	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]tree(伍一鸣)	最终得分	100
用户昵称	/k	是否通过	通过
代码语言	C++	运行时间	9.179 s
提交时间	2016-02-13 17:35:16	内存使用	3.85 MiB
显示代码纯文本
#include<iostream>
#include<cstdio>
#define mod 51061
#define ll unsigned int
using namespace std;
int n,l;
/*struct u
{
	int b;
	int x;
}c[200000];h[100010],*/
int f[100010];
unsigned int bjia[100010],bcheng[100010],w[100010],z[100010];
bool /*bv[100010],*/b[100010];
int Z[100010],Y[100010],st[100010];
int s[100010];
inline bool grt(int a)
{
	return (f[a]==0||(Z[f[a]]!=a&&Y[f[a]]!=a));
}
inline void gy(int x)
{
	int y=f[x];
	int z=f[y];
	if(Z[z]==y)
	    Z[z]=x;
	else
	    if(Y[z]==y)
	        Y[z]=x;
	 f[x]=z;
	 f[Y[x]]=y;
	 Z[y]=Y[x];
	 f[y]=x;
	 Y[x]=y;
}
inline void gz(int x)
{
	int y=f[x];
	int z=f[y];
	if(Z[z]==y)
	    Z[z]=x;
	else
	    if(Y[z]==y)
	        Y[z]=x;
	 f[x]=z;
	 f[Z[x]]=y;
	 Y[y]=Z[x];
	 f[y]=x;
	 Z[x]=y;
}
inline void Updata(int a)
{
	z[0]=w[0]=s[0]=0;
	z[a]=w[a]+z[Z[a]]+z[Y[a]];
	z[a]%=mod;
	s[a]=s[Z[a]]+s[Y[a]]+1;
}
inline void Pcheng(int a)
{
	if(bcheng[a]!=1)
	{
		if(Z[a])
		{
		//	if(bjia[Z[a]]>0)
			//	Pushdown(Z[a]);
			bcheng[Z[a]]*=bcheng[a];
			bcheng[Z[a]]%=mod;
			bjia[Z[a]]*=bcheng[a];
			bjia[Z[a]]%=mod;
			w[Z[a]]*=bcheng[a];
			w[Z[a]]%=mod;
			z[Z[a]]*=bcheng[a];
			z[Z[a]]%=mod;
		}
		if(Y[a])
		{
			//if(bjia[Y[a]])
			//	Pushdown(Y[a]);
			bcheng[Y[a]]*=bcheng[a];
			bcheng[Y[a]]%=mod;
			bjia[Y[a]]*=bcheng[a];
			bjia[Y[a]]%=mod;
			w[Y[a]]*=bcheng[a];
			w[Y[a]]%=mod;
			z[Y[a]]*=bcheng[a];
			z[Y[a]]%=mod;
		}
		bcheng[a]=1;
	}
}
inline void Pushdown(int a)
{
	if(a==0)
	    return;
	if(b[a])
	{
		b[a]=0;
		b[Z[a]]^=1;
		b[Y[a]]^=1;
		swap(Z[a],Y[a]);
	}
	Pcheng(a);
	if(bjia[a])
	{
		if(Z[a])
		{
			//if(bcheng[Z[a]]>1)
			//	Pushdown(Z[a]);
			bjia[Z[a]]+=bjia[a];
			bjia[Z[a]]%=mod;
			w[Z[a]]+=bjia[a];
			w[Z[a]]%=mod;
			z[Z[a]]+=bjia[a]*s[Z[a]];
			z[Z[a]]%=mod;
		}
		if(Y[a])
		{
			//if(bcheng[Y[a]]>1)
			//	Pushdown(Y[a]);
			bjia[Y[a]]+=bjia[a];
			bjia[Y[a]]%=mod;
			w[Y[a]]+=bjia[a];
			w[Y[a]]%=mod;
			z[Y[a]]+=bjia[a]*s[Y[a]];
			z[Y[a]]%=mod;
		}
		bjia[a]=0;
	}
	Updata(a);
}/*
inline void gj(int a,int b)
{
	c[++l].b=b;
	c[l].x=h[a];
	h[a]=l;
}*/
inline void Splay(int x)
{
	int y=x,t=1;
	st[t]=y;
	while(!grt(y))
	{
		y=f[y];
		st[++t]=y;
	}
	for(int i=t;i>=1;i--)
	    Pushdown(st[i]);
	for(int i=1;i<=t;i++)
	    Updata(st[i]);
	while(!grt(x))
	{
		y=f[x];
		if(Y[y]==x)
		    gz(x);
		else
		    gy(x);
		Updata(y);
		Updata(x);
	}
}
inline void Access(int x)
{
	int t=0;
	while(x)
	{
	//if(x==3)
	 //   printf("T%d %d\n",Z[1],grt(3));
		Splay(x);
		Y[x]=t;
		Updata(x);
		t=x;
		x=f[x];
	}
}
inline void Mroot(int x)
{
	Access(x);
	Splay(x);
	b[x]^=1;
}
inline void Link(int father,int son)
{
	Mroot(son);
	f[son]=father;
	Updata(son);
	Updata(father);
}/*
inline void gdfs(int a)
{
	bv[a]=1;
	for(int i=h[a];i;i=c[i].x)
	{
		int u=c[i].b;
		if(bv[u])
		    continue;
		Link(a,u);
		gdfs(u);
	}
}*/
inline void gjia()
{
	ll aa,bb,cc;
	scanf("%d%d%d",&aa,&bb,&cc);
	cc%=mod;
	Mroot(aa);
	Access(bb);
	Splay(aa);
	//if(bcheng[Y[aa]]>1)
	//	Pushdown(Y[aa]);
	Pcheng(aa);
	w[aa]+=cc;
	w[aa]%=mod;
	z[aa]+=cc*s[aa];
	z[aa]%=mod;
	bjia[aa]+=cc;
	bjia[aa]%=mod;
	Updata(aa);
}
inline void gcheng()
{
	ll aa,bb,cc;
	scanf("%d%d%d",&aa,&bb,&cc);
	cc%=mod;
	Mroot(aa);
	Access(bb);
	Splay(aa);
	//if(bjia[Y[aa]]!=0)
	//	Pushdown(Y[aa]);
	w[aa]*=cc;
	w[aa]%=mod;
	z[aa]*=cc;
	z[aa]%=mod;
	bcheng[aa]*=cc;
	bcheng[aa]%=mod;
	//printf("?%d ",cc);
	//for(int i=1;i<=n;i++)
	//    printf("N %d %d %d\n",i,Z[i],Y[i]);
	//printf("?%d\n",bcheng[2]);
	Updata(aa);
}
inline void gw()
{
	int aa,bb;
	scanf("%d%d",&aa,&bb);
	Mroot(aa);
	Access(bb);
	Splay(aa);
	printf("%d\n",z[aa]%mod);
}
inline void Cut(int father,int son)
{
	Mroot(son);
	Access(father);
	Splay(father);
	f[son]=0;
	Z[father]=0;
	Updata(son);
	Updata(father);
}
int main()
{
    freopen("nt2012_wym_tree.in","r",stdin);
	freopen("nt2012_wym_tree.out","w",stdout);
	int Q;
	scanf("%d",&n);
	scanf("%d",&Q);
	for(int i=0;i<=n;i++)
	    s[i]=bcheng[i]=z[i]=w[i]=1;
	for(int i=1;i<n;i++)
	{
		ll aa,bb;
		scanf("%d%d",&aa,&bb);
		Link(aa,bb);
	/*	bcheng[i]=1;
		z[i]=w[i]=1;*/
	}
	/*bcheng[0]=1;
	bcheng[n]=1;
	z[n]=w[n]=1;*/
	//printf("R%d %d\n",grt(3),Y[2]);
	while(Q--)
	{
		char ss[3];
		scanf("%s",ss);
		if(ss[0]=='R')
		    break;
		if(ss[0]=='+')
		{
			gjia();
		}
		else if(ss[0]=='-')
		{
			ll aa,bb,cc,dd;
			scanf("%d%d%d%d",&aa,&bb,&cc,&dd);
			Cut(aa,bb);
			Link(cc,dd);
		}
		else if(ss[0]=='*')
		{
			gcheng();
		}
		else
		{
			gw();
		}
	}
	//while(1);
}