记录编号	481365	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]tree(伍一鸣)	最终得分	100
用户昵称	Hallmeow	是否通过	通过
代码语言	C++	运行时间	3.569 s
提交时间	2018-01-02 15:58:58	内存使用	7.21 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <vector>
using namespace std;
#define pos(i,a,b) for(int i=(a);i<=(b);i++)
#define pos2(i,a,b) for(int i=(a);i>=(b);i--)
#define lc(x) (ch[x][0])
#define rc(x) (ch[x][1])
#define N 201000
#define int unsigned int
const int p=51061;
char xB[(1<<15)+10],*xS=xB,*xT=xB;
#define gtc (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++)
inline void read(int &xx){
    register char ch1=gtc;
    for(xx=0;ch1<'0'||ch1>'9';ch1=gtc);
    for(;ch1>='0'&&ch1<='9';xx=(xx<<1)+(xx<<3)+ch1-'0',ch1=gtc);
}
int fa[N],ch[N][2],size[N],reverse[N];
int add[N],sum[N],mul[N],v[N];
int get(int x){return rc(fa[x])==x;}
inline void update(int x){
	if(x){
		size[x]=size[lc(x)]+size[rc(x)]+1;
		sum[x]=(v[x]+sum[lc(x)]+sum[rc(x)])%p;
	}
}
inline void mark(int x,int y,int z){
	v[x]=(v[x]*z+y)%p;
	sum[x]=(sum[x]*z+size[x]*y)%p;
	add[x]=(add[x]*z+y)%p;
	mul[x]=(mul[x]*z)%p;
}
inline void pushdown(int x){
	if(x){
		if(reverse[x]){
			swap(lc(x),rc(x));
			if(lc(x)) reverse[lc(x)]^=1;
			if(rc(x)) reverse[rc(x)]^=1;
			reverse[x]=0;
		}
		if(add[x]!=0||mul[x]!=1){
			if(lc(x)) mark(lc(x),add[x],mul[x]);
			if(rc(x)) mark(rc(x),add[x],mul[x]);
			add[x]=0;mul[x]=1;
		}	
	}
}
inline int isroot(int x){return lc(fa[x])!=x&&rc(fa[x])!=x;}
inline void rotate(int x){
	int old=fa[x],oldf=fa[old],d=get(x);
	if(!isroot(old)) ch[oldf][rc(oldf)==old]=x;
	fa[x]=oldf;
	ch[old][d]=ch[x][d^1];
	fa[ch[old][d]]=old;
	ch[x][d^1]=old;fa[old]=x;
	update(old);update(x);
}
int stack[N],hea;
inline void splay(int x){
	hea=0;stack[++hea]=x;
	for(int i=x;!isroot(i);i=fa[i]) stack[++hea]=fa[i];
	pos2(i,hea,1) pushdown(stack[i]);
	for(int f;!isroot(x);rotate(x)){
		if(!isroot(f=fa[x])) rotate((get(x)==get(f))?f:x);
	}
}
inline void access(int x){for(int t=0;x;t=x,x=fa[x]){splay(x);rc(x)=t;update(x);}}
inline void makeroot(int x){access(x);splay(x);reverse[x]^=1;}
inline void link(int x,int y){makeroot(x);fa[x]=y;}
inline void cut(int x,int y){makeroot(x);access(y);splay(y);lc(y)=fa[x]=0;}
inline void Add(int x,int y,int z){makeroot(x);access(y);splay(y);mark(y,z,1);}
inline void Mul(int x,int y,int z){makeroot(x);access(y);splay(y);mark(y,0,z);}
inline int query(int x,int y){makeroot(x);access(y);splay(y);return sum[y];}
int n,q;
signed main(){
	freopen("nt2012_wym_tree.in","r",stdin);
	freopen("nt2012_wym_tree.out","w",stdout);
	read(n);read(q);
	pos(i,1,n) v[i]=mul[i]=1;
	pos(i,1,n-1){
		int x,y;read(x);read(y);
		link(x,y);
	}
	pos(i,1,q){
		char opt=gtc;
        while (opt!='+'&&opt!='-'&&opt!='*'&&opt!='/') opt=gtc;
		int x,y,z,w;read(x);read(y);
		if(opt=='+'){
			read(z);Add(x,y,z);continue;
		}
		if(opt=='-'){
			read(z);read(w);cut(x,y);link(z,w);continue;
		}
		if(opt=='*'){
			read(z);Mul(x,y,z);continue;
		}
		if(opt=='/'){
			printf("%d\n",query(x,y)%p);
		}
	}
	return 0;
}