记录编号	392090	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2012]tree(伍一鸣)	最终得分	100
用户昵称	可以的.	是否通过	通过
代码语言	C++	运行时间	7.495 s
提交时间	2017-04-07 07:42:00	内存使用	4.13 MiB

#include <stdio.h>
#include <ctime>
#include <algorithm>
#include <cstring>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <cmath>
#include <vector>
#define Mem(a, b) memset(a, b, sizeof a)
#define Mcpy(a, b) memcpy(a, b, sizeof a)
#define RG register
#define IL inline
using namespace std;
typedef long long LL;
typedef unsigned int uint;
typedef unsigned long long ull;
IL void qkin(RG int &res){
	RG int x,f=1; RG char ch;
	while(ch=getchar(),ch<'0'||ch>'9')if(ch=='-')f=-1;x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;res=x*f;}
IL void read(RG int &A){ qkin(A); }
IL void read(RG int &A,RG int &B){ qkin(A),qkin(B); }
IL void read(RG int &A,RG int &B,RG int &C){ qkin(A),qkin(B),qkin(C); }
#define Gets(s) scanf("%s", s+1);
const double INF = 1e60;
const int inf = 0x7f7f7f7f;
const double Pi = acos(-1);
const double eps = 1e-8;
const int maxn = 100010;
const int mod = 51061;

int n, m;
struct node{
	int sum, size, id, add, mul, data;
	bool tag;
	node *ch[2], *p;
	node(int _id = 0 , int d = 0){
		add = 0; mul = 1; data = d;
		id = _id; sum = d; size = 1; tag = 0;
	}
	void ref();
	void update();
	void retag();
	void upmul(int);
	void upadd(int);
}mem[maxn], *ptr = mem, *null;
void node::upadd(int x){
	add += x; data += x;
	sum += 1ll*size*x%mod;
	add%=mod; data%=mod; sum%=mod;
}
void node::upmul(int x){
	add = 1ll*add*x%mod;
	data = 1ll*data*x%mod;
	sum = 1ll*sum*x%mod;
	mul = 1ll*mul*x%mod;
}
void node::ref(){
	size = ch[0]->size + ch[1]->size + 1;
	sum = (ch[0]->sum + ch[1]->sum + data)%mod;
}
void node::retag(){ tag ^= 1; }
void node::update(){
	if(this == null) return;
	if(tag){
		if(ch[0] != null) ch[0]->retag();
		if(ch[1] != null) ch[1]->retag();
		swap(ch[0], ch[1]); retag();
	}
	if(mul != 1){
		if(ch[0] != null) ch[0]->upmul(mul);
		if(ch[1] != null) ch[1]->upmul(mul);
		mul = 1;
	}
	if(add){
		if(ch[0] != null) ch[0]->upadd(add);
		if(ch[1] != null) ch[1]->upadd(add);
		add = 0;
	}
}

void newnode(int,int);
void rot(node*,int);
void splay(node*);
void link(node*,node*);
void cut(node*,node*);
void makeroot(node*);
void access(node*);
int isroot(node*);
int islc(node*);
void Add(node*,node*,int);
void Mul(node*,node*,int);
int Sum(node*,node*);

int main(){
#define HAHA LALA
#ifdef HAHA
	freopen("nt2012_wym_tree.in", "r", stdin);
	freopen("nt2012_wym_tree.out", "w", stdout);
#endif

	null = ptr++; null->size = 0; null->data = 0;
	null->ch[0] = null->ch[1] = null->p = null;

	read(n, m);
	for(int i=1; i<=n; i++) newnode(i, 1);

	for(int i=1; i<n; i++){
		int x, y; read(x, y);
		link(mem + x, mem + y);
	}

	char op; int x, y, c;
	while(m--){
		scanf(" %c", &op); read(x, y);
		if(op == '+') {
			read(c);
			Add(mem + x, mem + y, c);
		} else if(op == '-'){
			cut(mem + x, mem + y);
			read(x, y);
			link(mem + x, mem + y);
		} else if(op == '*'){
			read(c);
			Mul(mem + x, mem + y, c);
		} else {
			int ans = Sum(mem + x, mem + y);
			printf("%d\n", ans);
		}
	}
	return 0;
}

void newnode(int i, int x){
	node* y = ptr++; *y = node(i, x);
	y->ch[0] = y->ch[1] = y->p = null;
}
void rot(node* x,int d){
	node *y = x->ch[d^1];
	if(!isroot(x)) x->p->ch[islc(x)^1] = y;
	y->p = x->p;
	x->ch[d^1] = y->ch[d];
	if(y->ch[d] != null) y->ch[d]->p = x;
	y->ch[d] = x;
	x->p = y;
	x->ref(); y->ref();
} 
void splay(node *x){
	x->update();
	for(node* rt=x->p; !isroot(x); rt=x->p){
		if(!isroot(rt)) rt->p->update();
		rt->update(); x->update();
		if(isroot(rt)){
			rot(rt, islc(x)); return;
		}
		if(islc(x) == islc(rt)) rot(rt->p, islc(x));
		else rot(rt, islc(x));
		rot(x->p, islc(x));
	}
}
int isroot(node* x){
	if(x->p == null) return 1;
	if(x->p->ch[0] == x || x->p->ch[1] == x) return 0;
	return 1;
}
int islc(node *x){ return x == x->p->ch[0]; }
void access(node *x){
	node *y = null;
	while(x != null){
		splay(x);
		x->ch[1] = y;
		x->ref();
		y = x; x = x->p;
	}
}
void makeroot(node *x){
	access(x); splay(x); x->retag();
}
void link(node *x,node *y){
	makeroot(x); x->p = y;
}
void cut(node *x,node *y){
	makeroot(x); access(y); splay(y);
	y->ch[0] = y->ch[0]->p = null; y->ref();
}
void Add(node *x,node *y,int c){
	makeroot(x); access(y); splay(y);
	y->upadd(c);
}
void Mul(node *x,node *y,int c){
	makeroot(x); access(y); splay(y);
	y->upmul(c);
}
int Sum(node *x,node *y){
	makeroot(x); access(y); splay(y);
	return y->sum;
}

/*
3 2333
1 2
2 3
* 1 3 4
/ 1 1
/ 3 1
 */