更好的阅读体验:https://www.cnblogs.com/To-Carpe-Diem/p/19626423

大意

动态维护树上的乘积和加和。

思路

直接 $\text{LCT}$ 维护即可，但是注意乘法和加法的混合的下传。

代码

#include<iostream>
using namespace std;

#define uint unsigned int
#define lc(x) t[x].ch[0]
#define rc(x) t[x].ch[1]
#define fa(x) t[x].fa
const int MAXN = 1e5 + 5;
const int MOD = 51061;

struct node{
	int ch[2], fa;
	uint val, sum, sz, add, mul;
	bool tag;
	node(){
		ch[1] = ch[0] = fa = 0;
		val = sum = sz = add = 0;
		mul = 1;
		tag = false;
	}
}t[MAXN];

bool isroot(int x){
	return (lc(fa(x)) != x) && (rc(fa(x)) != x);
}

void pushup(int x){
	t[x].sz = t[lc(x)].sz + t[rc(x)].sz + 1;
	t[x].sum = (t[lc(x)].sum + t[rc(x)].sum + t[x].val) % MOD;
}

void update_rev(int x){
	if(!x) return;
	swap(lc(x), rc(x));
	t[x].tag ^= 1;
}

void apply(int x, uint md, uint ad){
	if(!x) return;
	t[x].val = (1LL * t[x].val * md + ad) % MOD;
	t[x].sum = (1LL * t[x].sum * md + 1LL * ad * t[x].sz) % MOD;
	t[x].mul = (1LL * t[x].mul * md) % MOD;
	t[x].add = (1LL * t[x].add * md + ad) % MOD;
}

void pushdown(int x){
	if(t[x].tag){
		update_rev(lc(x));
		update_rev(rc(x));
		t[x].tag = 0;
	}
	if(t[x].mul != 1 || t[x].add != 0){
		apply(lc(x), t[x].mul, t[x].add);
		apply(rc(x), t[x].mul, t[x].add);
		t[x].mul = 1, t[x].add = 0;
	}
}

void rotate(int x){
	int y = fa(x), z = fa(y);
	int k = (rc(y) == x);
	if(!isroot(y)){
		t[z].ch[rc(z) == y] = x;
	}
	fa(x) = z;
	t[y].ch[k] = t[x].ch[k ^ 1];
	if(t[x].ch[k ^ 1]){
		fa(t[x].ch[k ^ 1]) = y;
	}
	t[x].ch[k ^ 1] = y;
	fa(y) = x;
	pushup(y);
	pushup(x);
}

void pushshell(int x){
	if(!isroot(x)){
		pushshell(fa(x));
	}
	pushdown(x);
}

void splay(int x){
	pushshell(x);
	while(!isroot(x)){
		int y = fa(x), z = fa(y);
		if(!isroot(y)){
			(rc(z) == y) ^ (rc(y) == x) ? rotate(x) : rotate(y);
		}
		rotate(x);
	}
}

void access(int x){
	for(int y = 0;x;y = x, x = fa(x)){
		splay(x);
		rc(x) = y;
		pushup(x);
	}
}

void makeroot(int x){
	access(x);
	splay(x);
	update_rev(x);
}

int findrt(int x){
	access(x);
	splay(x);
	while(lc(x)){
		pushdown(x);
		x = lc(x);
	}
	splay(x);
	return x;
}

void split(int x, int y){
	makeroot(x);
	access(y);
	splay(y);
}

void link(int x, int y){
	makeroot(x);
	if(findrt(y) != x) fa(x) = y;
}

void cut(int u1, int v1){
	split(u1, v1);
	if(lc(v1) == u1 && rc(u1) == 0){
		fa(u1) = lc(v1) = 0;
		pushup(v1);
	}
}

int main(){
	int n, q;
	cin >> n >> q;
	for(int i = 1;i <= n;i ++){
		t[i].val = t[i].sum = t[i].sz = 1;
		t[i].mul = 1;
	}
	for(int i = 1;i < n;i ++){
		int u, v; cin >> u >> v;
		link(u, v);
	}
	while(q --){
		char op; cin >> op;
		int u, v, u2, v2; uint c;
		if(op == '+'){
			cin >> u >> v >> c;
			split(u, v);
			apply(v, 1, c);
		}
		else if(op == '-'){
			cin >> u >> v >> u2 >> v2;
			cut(u, v);
			link(u2, v2);
		}
		else if(op == '*'){
			cin >> u >> v >> c;
			split(u, v);
			apply(v, c, 0);
		}
		else if(op == '/'){
			cin >> u >> v;
			split(u, v);
			cout << t[v].sum << endl;
		}
	}
	return 0;
}