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

#include<iostream>
#include<cstdio>
using namespace std;
typedef unsigned int UI;
const int maxn = 1e5+10;
const int lcy = 51061;

class link_cut_tree {
private:
	struct node{
		int ls, rs, fa, size;
		bool revc;
		UI mul, add, sum, v;
		node() {
			ls = rs = fa = add = revc = 0;
			size = sum = mul = v = 1;
		}
	}ns[maxn];
	
	inline void make_mul(int tar, int v) {
		if(!tar) return;
		ns[tar].v	= (ns[tar].v * v) 	% lcy;
		ns[tar].sum = (ns[tar].sum * v) % lcy;
		ns[tar].add = (ns[tar].add * v) % lcy;
		
		ns[tar].mul = (ns[tar].mul * v) % lcy;
	}
	
	inline void make_add(int tar, int v) {
		if(!tar) return;
		ns[tar].v	= (ns[tar].v + v) % lcy;
		ns[tar].sum = (ns[tar].sum + ns[tar].size * v) % lcy;
		
		ns[tar].add = (ns[tar].add + v) % lcy;
	}
	
	inline void make_revc(int tar) {
		if(!tar) return;
		swap(ns[tar].ls, ns[tar].rs);
		
		ns[tar].revc ^= 1;
	}
	
	inline void update(int tar) {
		if(!tar) return;
		ns[tar].size = ns[ns[tar].ls].size + ns[ns[tar].rs].size + 1;
		ns[tar].sum  = ns[ns[tar].ls].sum % lcy + ns[ns[tar].rs].sum % lcy  + ns[tar].v;
		ns[tar].sum %= lcy;
	}
	
	inline void push_down(int tar) {
		if(!tar) return;
		if(ns[tar].mul != 1) {
			make_mul(ns[tar].ls, ns[tar].mul);
			make_mul(ns[tar].rs, ns[tar].mul);
			ns[tar].mul = 1;
		}
		if(ns[tar].add) {
			make_add(ns[tar].ls, ns[tar].add);
			make_add(ns[tar].rs, ns[tar].add);
			ns[tar].add = 0; 
		}
		if(ns[tar].revc) {
			make_revc(ns[tar].ls);
			make_revc(ns[tar].rs);
			ns[tar].revc ^= 1;
		}
	}
	
	inline void zig(int &tar) {
		int fa = ns[tar].fa;
		if(ns[ns[fa].fa].ls == fa) ns[ns[fa].fa].ls = tar;
		if(ns[ns[fa].fa].rs == fa) ns[ns[fa].fa].rs = tar;
		ns[tar].fa = ns[fa].fa;
		ns[ns[tar].rs].fa = fa;
		ns[fa].ls = ns[tar].rs;
		ns[tar].rs = fa, ns[fa].fa = tar;
		update(fa);
	} 
	
	inline void zag(int &tar) {
		int fa = ns[tar].fa;
		if(ns[ns[fa].fa].ls == fa) ns[ns[fa].fa].ls = tar;
		if(ns[ns[fa].fa].rs == fa) ns[ns[fa].fa].rs = tar;
		ns[tar].fa = ns[fa].fa;
		ns[ns[tar].ls].fa = fa;
		ns[fa].rs = ns[tar].ls;
		ns[tar].ls = fa, ns[fa].fa = tar;
		update(fa);
	}
	
	inline bool is_root(int &tar) {
		int fa = ns[tar].fa;
		return ns[fa].ls != tar && ns[fa].rs != tar;
	}


	void outer(int now) {
		printf("now = %d ls = %d rs = %d fa = %d v = %d sum = %d\n",
		now, ns[now].ls, ns[now].rs, ns[now].fa, ns[now].v, ns[now].sum);
	}


	void out() {
		printf("\n");
		for(int i = 0; i <= 3; i++) {
			outer(i);
		}
	}


	inline void splay(int now) {
		int fa;
		bool done = false;
		push_down(now);
		while(!is_root(now)) {
			fa = ns[now].fa;
			push_down(ns[fa].fa), push_down(fa), push_down(now);
			if(is_root(fa)) {
				ns[fa].ls == now ? zig(now) : zag(now);
				break;
			}
			else {
				if(ns[ns[fa].fa].ls == fa) ns[fa].ls == now ? zig(fa) : zag(now), zig(now);
				else ns[fa].rs == now ? zag(fa) : zig(now), zag(now);
			}
		}
		update(now);
	}
	


	inline void access(int tar) {
		int la = 0;
		while(tar) {
			splay(tar);
			ns[tar].rs = la;
			update(tar);
			la = tar;
			tar = ns[tar].fa;
		}
	}

	inline void make_root(int tar) {
		access(tar);
		splay(tar);
		make_revc(tar);
	}
	
public:
	link_cut_tree() { ns[0].sum = ns[0].mul = ns[0].v = ns[0].size = 0; }
	
	inline void link(int u, int v) {
		make_root(v);
		ns[v].fa = u;
	}
	
	inline void cut(int u, int v) {
		make_root(u); access(v); splay(u);
		ns[u].rs = 0, ns[v].fa = 0;
		update(u);
	}
	
	inline void change_add(int u, int v, int c) {
		make_root(u); access(v); splay(v);
		make_add(v, c);
	} 
	
	inline void change_mul(int u, int v, int c) {
		make_root(u); access(v); splay(v);
		make_mul(v, c);
	}
	
	inline int query(int u, int v) {
		make_root(u); access(v); splay(v);
		return ns[v].sum;
	}

}lct;

inline int get_num() {
	int ans = 0;
	char tmp = getchar();
	while(tmp < '0' || tmp > '9') tmp = getchar();
	while(tmp >= '0' && tmp <= '9') {
		ans = ans*10 + tmp - '0';
		tmp = getchar(); 
	}
	return ans;
}

inline char get_han() {
	char tmp = getchar();
	while(tmp != '*' && tmp != '/' && tmp != '+' && tmp != '-') tmp = getchar();
	return tmp;
} 

int n, q;

inline void read() {
	n = get_num(); q = get_num();
	int u, v;
	for(int i = 1; i <= n-1; i++) {
		u = get_num(), v = get_num();
		lct.link(u, v);
	}
}

inline void solve() {
	char han;
	int u, v, c;
	for(int i = 1; i <= q; i++) {
		han = get_han();
		if(han == '+') {
			u = get_num(), v = get_num(), c = get_num();
			lct.change_add(u, v, c);
		} else if(han == '-') {
			u = get_num(), v = get_num();
			lct.cut(u, v);
			u = get_num(), v = get_num();
			lct.link(u, v);
		} else if(han == '*') {
			u = get_num(), v = get_num(), c = get_num();
			lct.change_mul(u, v, c); 
		} else if(han == '/') {
			u = get_num(), v = get_num(), c = lct.query(u, v);
			printf("%d\n", c);
		}
	}
}

int main() {
	freopen("nt2012_wym_tree.in", "r", stdin);
	freopen("nt2012_wym_tree.out", "w", stdout);
	read();
	solve();
	return 0;
}