记录编号	143521	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]tree(伍一鸣)	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	13.623 s
提交时间	2014-12-15 17:12:21	内存使用	5.65 MiB

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<cmath>
#define CL(x) memset(x,0,sizeof(x))
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define dow(i,s,t) for(int i=(s);i>=(t);i--)
using namespace std;
typedef long long LL;
LL read(){
	LL ret=0,f=1;
	char x=getchar();
	while(!(x>='0' && x<='9')){if(x=='-')f=-1;x=getchar();}
	while(x>='0' && x<='9') ret=ret*10+x-'0', x=getchar();
	return ret*f;
}
char get_char(){
	char x=getchar();
	while(!(x=='+' || x=='-' || x=='*' || x=='/')) x=getchar();
	return x;
}
 
const int MAXN=1e5+10;
const int MOD=51061;
 
struct node{
	int ls,rs,fa;
	LL sz,val,sum,mul,add;
	bool revc;
	node(){ val=sum=mul=sz=1; }
}t[MAXN];
void push_up(int n){
	if(!n) return;
	t[n].sum=(t[t[n].ls].sum+t[t[n].rs].sum+t[n].val)%MOD;
	t[n].sz=t[t[n].ls].sz+t[t[n].rs].sz+1;
}
void node_mul(int n,int val){
	if(!n) return;
	t[n].val=(t[n].val*val)%MOD;
	t[n].sum=(t[n].sum*val)%MOD;
	t[n].mul=(t[n].mul*val)%MOD;
	t[n].add=(t[n].add*val)%MOD;
}
void node_add(int n,int val){
	if(!n) return;
	t[n].val=(t[n].val+val)%MOD;
	t[n].sum=(t[n].sum+val*t[n].sz)%MOD;
	t[n].add=(t[n].add+val)%MOD;
}
void push_down(int n){
	if(t[n].mul!=1){
		node_mul(t[n].ls,t[n].mul);
		node_mul(t[n].rs,t[n].mul);
		t[n].mul=1;
	}
	if(t[n].add){
		node_add(t[n].ls,t[n].add);
		node_add(t[n].rs,t[n].add);
		t[n].add=0;
	}
	if(t[n].revc){
		swap(t[n].ls,t[n].rs);
		if(t[n].ls) t[t[n].ls].revc^=1;
		if(t[n].rs) t[t[n].rs].revc^=1;
		t[n].revc^=1;
	}
}
void zig(int x){
	int y=t[x].fa, z=t[y].fa;
	if(t[z].ls==y) t[z].ls=x;
	if(t[z].rs==y) t[z].rs=x;
	t[x].fa=z;
	t[y].ls=t[x].rs, t[t[x].rs].fa=y;
	t[x].rs=y, t[y].fa=x;
	push_up(y), push_up(x);
}
void zag(int x){
	int y=t[x].fa, z=t[y].fa;
	if(t[z].ls==y) t[z].ls=x;
	if(t[z].rs==y) t[z].rs=x;
	t[x].fa=z;
	t[y].rs=t[x].ls, t[t[x].ls].fa=y;
	t[x].ls=y,  t[y].fa=x;
	push_up(y), push_up(x);
}
bool is_root(int x){
	int f=t[x].fa;
	return t[f].ls!=x && t[f].rs!=x;
}
void splay(int n){
	int x=n;
	push_down(x);
	while(!is_root(x)){
		int y=t[x].fa, z=t[y].fa;
		push_down(z), push_down(y), push_down(x);
		if(is_root(y)){
			if(t[y].ls==x) zig(x);
			else zag(x);
			break;
		}else if(t[z].ls==y){
			if(t[y].ls==x) zig(y), zig(x);
			else zag(x), zig(x);
		}else{
			if(t[y].rs==x) zag(y), zag(x);
			else zig(x), zag(x);
		}
	}
}
void access(int x){
	int y=0;
	while(x){
		splay(x);
		t[x].rs=y;
		push_up(x);
		y=x;
		x=t[x].fa;
	}
}
void make_root(int x){
	access(x);
	splay(x);
	t[x].revc^=1;
}
void link(int u,int v){
	make_root(v);
	splay(v);
	t[v].fa=u;
}
void cut(int u,int v){
	make_root(u);
	access(v);
	splay(u);
	t[u].rs=0;
	t[v].fa=0;
	push_up(u);
}
void add(int u,int v,int c){
	make_root(u);
	access(v);
	splay(v);
	node_add(v,c);
}
void mul(int u,int v,int c){
	make_root(u);
	access(v);
	splay(v);
	node_mul(v,c);
}
int query(int u,int v){
	make_root(u);
	access(v);
	splay(v);
	return t[v].sum;
}
 
int N,Q;
int main(){
	//freopen("in.txt","r",stdin);
	//freopen("1.out","w",stdout);
	freopen("nt2012_wym_tree.in","r",stdin);
	freopen("nt2012_wym_tree.out","w",stdout);
	t[0].val=t[0].sum=t[0].mul=t[0].sz=0;
	N=read(), Q=read();
	rep(i,1,N-1){
		int u=read(), v=read();
		link(u,v);
	}
	rep(i,1,Q){
		char op=get_char();
		if(op=='+'){
			int u=read(), v=read(), c=read();
			add(u,v,c);
		}else if(op=='-'){
			int u1=read(), v1=read(), u2=read(), v2=read();
			cut(u1,v1);
			link(u2,v2);
		}else if(op=='*'){
			int u=read(), v=read(), c=read();
			mul(u,v,c);
		}else{
			int u=read(), v=read();
			printf("%d\n",query(u,v));
		}
	}
	return 0;
}