记录编号	367300	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]tree(伍一鸣)	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	4.428 s
提交时间	2017-01-29 20:24:01	内存使用	3.72 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define isroot(x) ((x)->p==null||((x)!=(x)->p->ch[0]&&(x)!=(x)->p->ch[1]))
#define dir(x) ((x)==(x)->p->ch[1])
using namespace std;
const int maxn=100010;
const unsigned M=51061;
struct node{
	unsigned data,sum,a,b;
	int size;
	bool rev;
	node *ch[2],*p;
	node(unsigned d=0):data(d),sum(d),a(1),b(0),size(1),rev(false){}
	void add(unsigned d){
		data=(data+d)%M;
		sum=(sum+(unsigned)size%M*d%M)%M;
		b=(b+d)%M;
	}
	void mul(unsigned d){
		data=data*d%M;
		sum=sum*d%M;
		a=a*d%M;
		b=b*d%M;
	}
	void pushdown(){
		if(a!=1){
			ch[0]->mul(a);
			ch[1]->mul(a);
			a=1;
		}
		if(b){
			ch[0]->add(b);
			ch[1]->add(b);
			b=0;
		}
		if(rev){
			ch[0]->rev^=true;
			ch[1]->rev^=true;
			swap(ch[0],ch[1]);
			rev=false;
		}
	}
	void refresh(){
		sum=((ch[0]->sum+ch[1]->sum)%M+data)%M;
		size=ch[0]->size+ch[1]->size+1;
	}
}null[maxn];
void add(node*,node*,unsigned);
void mul(node*,node*,unsigned);
unsigned qsum(node*,node*);
void link(node*,node*);
void cut(node*,node*);
node *access(node*);
void makeroot(node*);
void splay(node*);
void clear(node*);
void rot(node*,int);
unsigned d;
char c;
int n,m,x,y;
int main(){
	freopen("nt2012_wym_tree.in","r",stdin);
	freopen("nt2012_wym_tree.out","w",stdout);
	null->size=0;
	null->ch[0]=null->ch[1]=null->p=null;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		null[i]=node(1);
		null[i].ch[0]=null[i].ch[1]=null[i].p=null;
	}
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		link(null+x,null+y);
	}
	while(m--){
		scanf(" %c%d%d",&c,&x,&y);
		if(c=='+'){
			scanf("%u",&d);
			add(null+x,null+y,d);
		}
		else if(c=='-'){
			cut(null+x,null+y);
			scanf("%d%d",&x,&y);
			link(null+x,null+y);
		}
		else if(c=='*'){
			scanf("%u",&d);
			mul(null+x,null+y,d);
		}
		else printf("%u\n",qsum(null+x,null+y));
	}
	return 0;
}
void add(node *x,node *y,unsigned d){
	makeroot(x);
	access(y)->add(d);
}
void mul(node *x,node *y,unsigned d){
	makeroot(x);
	access(y)->mul(d);
}
unsigned qsum(node *x,node *y){
	makeroot(x);
	return access(y)->sum;
}
void link(node *x,node *y){
	makeroot(x);
	splay(x);
	x->p=y;
}
void cut(node *x,node *y){
	makeroot(x);
	access(y);
	splay(y);
	y->ch[0]->p=null;
	y->ch[0]=null;
	y->refresh();
}
node *access(node *x){
	node *y=null;
	while(x!=null){
		splay(x);
		x->ch[1]=y;
		(y=x)->refresh();
		x=x->p;
	}
	return y;
}
void makeroot(node *x){access(x)->rev^=true;}
void splay(node *x){
	clear(x);
	while(!isroot(x)){
		if(isroot(x->p)){
			rot(x->p,dir(x)^1);
			break;
		}
		if(dir(x)==dir(x->p))rot(x->p->p,dir(x->p)^1);
		else rot(x->p,dir(x)^1);
		rot(x->p,dir(x)^1);
	}
}
void clear(node *x){
	if(!isroot(x))clear(x->p);
	x->pushdown();
}
void rot(node *x,int d){
	node *y=x->ch[d^1];
	if((x->ch[d^1]=y->ch[d])!=null)y->ch[d]->p=x;
	y->p=x->p;
	if(!isroot(x))x->p->ch[dir(x)]=y;
	(y->ch[d]=x)->p=y;
	x->refresh();
	y->refresh();
}