wy's Blog

2631: tree

Description

Input

Output

Sample Input

Sample Output

HINT

锻炼代码的动态树 +1

Time for 锻炼 代码 ability ...  不要问我为什么用一半英文

#include <cstdio>
#include <algorithm>
using namespace std;
#define LL long long
const int MaxN = 100010;
const int Mod = 51061;
int N, Q;
struct point{
	int fa, l, r, rev, key, sum, size, tlu, mul;
	point () {
	    fa = l = r = rev = tlu = 0;
		key = sum = size = mul = 1; 
	} 
	#define l(x)    (p[x].l)
	#define r(x)    (p[x].r)
	#define fa(x)   (p[x].fa)
	#define rev(x)  (p[x].rev)
	#define key(x)  (p[x].key)
	#define sum(x)  (p[x].sum)
	#define tlu(x)  (p[x].tlu)
	#define mul(x)  (p[x].mul) 
	#define size(x) (p[x].size)
}p[MaxN];
int que[MaxN], q;
bool isRoot(int x) {
	return !fa(x) || l(fa(x)) != x && r(fa(x)) != x;
}
bool which(int x) {
	return x == r(fa(x));
}
void Mul(int x, int k) {
	key(x) = (LL)key(x) * k % Mod; 
	sum(x) = (LL)sum(x) * k % Mod;
	tlu(x) = (LL)tlu(x) * k % Mod;
	mul(x) = (LL)mul(x) * k % Mod;
}
void Tlu(int x, int k) {
	key(x) = (key(x) + k) % Mod;
	sum(x) = ((LL)k * size (x) +sum(x)) % Mod;
	tlu(x) = (tlu(x) + k) % Mod;
}
void Rev(int x) {
	swap(l(x), r(x));
	rev(x) ^= 1;
}
void Down(int x) {
	if (rev(x)) {
		if (l(x)) Rev(l(x));
		if (r(x)) Rev(r(x));
		rev(x) = 0;
	}
	if (mul(x) ^ 1) {
		if (l(x)) Mul(l(x), mul(x));
		if (r(x)) Mul(r(x), mul(x));
		mul(x) = 1;
	}
	if (tlu(x)) {
		if (l(x)) Tlu(l(x), tlu(x));
		if (r(x)) Tlu(r(x), tlu(x));
		tlu(x) = 0;
	}
}
void Up(int x) {
	sum(x) = (( l(x) ? sum(l(x)) : 0 ) + ( r(x) ? sum(r(x)) : 0 ) + key(x) ) % Mod;
	size(x) = ( l(x) ? size(l(x)) : 0 ) + ( r(x) ? size(r(x)) : 0 ) + 1;
}
void Turn(int x) {
	int y = fa(x), z = fa(y), w = l(y) == x ? r(x) : l(x);
	fa(x) = z; if (!isRoot(y)) (l(z) == y ? l(z) : r(z)) = x;
	fa(y) = x; (l(y) == x ? r(x) : l(x)) = y;
	if (w) fa(w) = y; (l(y) == x ? l(y) : r(y)) = w;
	Up(y), Up(x);
}
void Splay(int x) {
	que[q = 0] = x;
	for (int y = x; !isRoot(y); y = fa(y)) que[++q] = fa(y);
	for (; q >= 0; --q) Down(que[q]);
	while (!isRoot(x)) {
		if (!isRoot(fa(x)))
		    if (which(fa(x)) == which(x)) Turn(fa(x));
		    else Turn(x);
		Turn(x);
	}
}
void access(int x) {
	for (int y = 0; x; y = x, x = fa(x)) 
	    Splay(x), r(x) = y, Up(x);
}
void MakeRoot(int x) {
	access(x), Splay(x);
	Rev(x);
}
int findRoot(int x) {
	access(x), Splay(x);
	int y = x, k;
	while (Down(y), l(y)) y = l(y);
	k = y;
	while (y != x) Up(fa(y)), y = fa(y);
	return k; 
}
void Link(int x, int y) {
	MakeRoot(x);
	fa(x) = y; 
}
void Delete(int x, int y) {
	MakeRoot(x), access(y), Splay(y);
	l(y) = 0, fa(x) = 0, Up(y);
}
int Get() {
	char Ch;
	int Sign = 1;
	while ((Ch = getchar()) < '0' || Ch > '9')
	    if (Ch == '-') Sign = -1;
	int Num = Ch - '0';
	while ((Ch = getchar()) >= '0' && Ch <= '9')
	    Num = Num * 10 + Ch - '0';
	return Num * Sign;
}
int main()
{
	scanf("%d%d", &N, &Q);
	for (int i = 1; i < N; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		Link(x, y);
	}
	for (int i = 1; i <= Q; ++i) {
		char ch;
		while ((ch = getchar()) != '+' && ch != '-' && ch != '*' && ch != '/');
		if (ch == '+') {
			int x = Get(), y = Get(), w = Get();
			MakeRoot(x), access(y), Splay(y);
			Tlu(y, w);
		}
		else
		    if (ch == '-') {
		    	Delete(Get(), Get());
		    	Link(Get(), Get());
			}
			else 
				if (ch == '*') {
					int x = Get(), y = Get(), w = Get();
					MakeRoot(x), access(y), Splay(y);
					Mul(y, w);
				}
				else {
					int x = Get(), y = Get();
					MakeRoot(x), access(y), Splay(y);
					printf("%d\n", sum(y));
				}
	} 
}