记录编号	170706	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]tree(伍一鸣)	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	7.932 s
提交时间	2015-07-15 10:10:20	内存使用	3.75 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef unsigned US;
const int SIZEN=100010;
const US MOD=51061;
int N,Q;
class Node{
public:
	int lc,rc,fa;
	US sz,val,sum,mul,add;
	//子树规模,点权,和,乘法标记,加法标记
	//先乘后加
	bool rev;//翻转标记
	Node(){sz=val=sum=mul=1;}
	#define lc(x) Tree[x].lc
	#define rc(x) Tree[x].rc
	#define fa(x) Tree[x].fa
	#define sz(x) Tree[x].sz
	#define val(x) Tree[x].val
	#define sum(x) Tree[x].sum
	#define mul(x) Tree[x].mul
	#define add(x) Tree[x].add
	#define rev(x) Tree[x].rev
};
Node Tree[SIZEN];
bool Is_Root(int x){return lc(fa(x))!=x&&rc(fa(x))!=x;}
void Update(int x){
	if(!x) return;
	sum(x)=(sum(lc(x))+sum(rc(x))+val(x))%MOD;
	sz(x)=sz(lc(x))+sz(rc(x))+1;
}
void Node_Mul(int x,US t){//子树*t
	if(!x) return;
	val(x)=(val(x)*t)%MOD;
	sum(x)=(sum(x)*t)%MOD;
	mul(x)=(mul(x)*t)%MOD;
	add(x)=(add(x)*t)%MOD;
}
void Node_Add(int x,US t){//子树+t
	if(!x) return;
	val(x)=(val(x)+t)%MOD;
	sum(x)=(sum(x)+t*sz(x))%MOD;
	add(x)=(add(x)+t)%MOD;
}
void Push_Down(int x){
	if(mul(x)!=1){
		Node_Mul(lc(x),mul(x));
		Node_Mul(rc(x),mul(x));
		mul(x)=1;
	}
	if(add(x)){
		Node_Add(lc(x),add(x));
		Node_Add(rc(x),add(x));
		add(x)=0;
	}
	if(rev(x)){
		swap(lc(x),rc(x));
		if(lc(x)) rev(lc(x))^=1;
		if(rc(x)) rev(rc(x))^=1;
		rev(x)=0;
	}
}
void Zig(int x){//右旋
	int y=fa(x),z=fa(y);
	if(lc(z)==y) lc(z)=x;
	if(rc(z)==y) rc(z)=x;
	fa(x)=z;
	lc(y)=rc(x);fa(lc(y))=y;
	rc(x)=y;fa(y)=x;
	Update(y);Update(x);
}
void Zag(int x){//左旋
	int y=fa(x),z=fa(y);
	if(lc(z)==y) lc(z)=x;
	if(rc(z)==y) rc(z)=x;
	fa(x)=z;
	rc(y)=lc(x);fa(rc(y))=y;
	lc(x)=y;fa(y)=x;
	Update(y);Update(x);
}
void Splay(int x){
	Push_Down(x);
	while(!Is_Root(x)){
		int y=fa(x),z=fa(y);
		Push_Down(z);Push_Down(y);Push_Down(x);
		if(Is_Root(y)){
			if(lc(y)==x) Zig(x);
			else Zag(x);
			return;
		}
		else if(lc(z)==y){
			if(lc(y)==x) Zig(y),Zig(x);
			else Zag(x),Zig(x);
		}
		else{
			if(rc(y)==x) Zag(y),Zag(x);
			else Zig(x),Zag(x);
		}
	}
}
void Access(int x){
	int y=0;
	while(x){
		Splay(x);
		rc(x)=y;
		Update(x);
		y=x;
		x=fa(x);
	}
}
void Make_Root(int x){
	Access(x);
	Splay(x);
	rev(x)^=1;
}
void Link(int x,int y){
	Make_Root(y);
	fa(y)=x;
}
void Cut(int x,int y){
	Make_Root(x);
	Access(y);
	Splay(y);
	fa(lc(y))=0;lc(y)=0;
	Update(y);
}
void Path_Add(int x,int y,US t){
	Make_Root(x);
	Access(y);
	Splay(y);
	Node_Add(y,t);
}
void Path_Mul(int x,int y,US t){
	Make_Root(x);
	Access(y);
	Splay(y);
	Node_Mul(y,t);
}
int Path_Query(int x,int y){
	Make_Root(x);
	Access(y);
	Splay(y);
	return sum(y);
}
void read(void){
	val(0)=sum(0)=mul(0)=sz(0)=0;
	int a,b;
	scanf("%d%d",&N,&Q);
	for(int i=1;i<N;i++){
		scanf("%d%d",&a,&b);
		Link(a,b);
	}
}
void work(void){
	char cmd[10];
	int x,y,x1,y1,t;
	for(int i=1;i<=Q;i++){
		scanf("%s",cmd);
		if(cmd[0]=='+'){
			scanf("%d%d%d",&x,&y,&t);
			Path_Add(x,y,t);
		}
		else if(cmd[0]=='-'){
			scanf("%d%d%d%d",&x,&y,&x1,&y1);
			Cut(x,y);
			Link(x1,y1);
		}
		else if(cmd[0]=='*'){
			scanf("%d%d%d",&x,&y,&t);
			Path_Mul(x,y,t);
		}
		else if(cmd[0]=='/'){
			scanf("%d%d",&x,&y);
			printf("%d\n",Path_Query(x,y));
		}
	}
}
int main(){
	freopen("nt2012_wym_tree.in","r",stdin);
	freopen("nt2012_wym_tree.out","w",stdout);
	read();
	work();
	return 0;
}