代码

#include <bits/stdc++.h>
using namespace std;

#define int long long

inline int read(){
	int sum=0,f=0;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar()){
		f |= (ch=='-');
	}
	for(;isdigit(ch);ch=getchar()){
		sum = ((sum<<3) + (sum<<1) + (ch^48));
	}
	return f?-sum:sum;
}

const int maxn = 505000;
const int mod = 51061;

int n,m,cnt,a[maxn];
int c[maxn][2],fa[maxn],val[maxn],size[maxn],add[maxn],mul[maxn],w[maxn],tag[maxn],st[maxn];

struct LCT{
	void pushup(int x){
		val[x] = (val[c[x][0]] + val[c[x][1]] + w[x]) %mod;
		size[x] = size[c[x][0]] + size[c[x][1]] + 1;
	}
	void pusha(int x,int y){
		val[x] = (val[x] + size[x]*y%mod) %mod;
		w[x] += y; w[x] %= mod;
		add[x] += y; add[x] %= mod;
	}
	void pushm(int x,int y){
		val[x] *= y; val[x] %= mod;
		w[x] *= y; w[x] %= mod;
		add[x] *= y; add[x] %= mod;
		mul[x] *= y; mul[x] %= mod;
	}
	void pushdown(int x){
		if(mul[x] != 1){
			pushm(c[x][0] , mul[x]); pushm(c[x][1] , mul[x]);
			mul[x] = 1;
		}
		if(add[x]){
			pusha(c[x][0] , add[x]); pusha(c[x][1] , add[x]);
			add[x] = 0;
		} 
		if(tag[x]){
			tag[c[x][0]] ^= 1; tag[c[x][1]] ^= 1;
			tag[x] = 0;
			swap(c[x][0] , c[x][1]);
		}
		val[x] %= mod;
		w[x] %= mod;
	}
	bool isroot(int x){
		return ((c[fa[x]][0] != x) && (c[fa[x]][1] != x));
	}
	void rotate(int x){
		int y = fa[x], z = fa[y], fl = (c[y][1]==x);
		fa[x] = z;
		if(!isroot(y)){
			c[z][c[z][1]==y] = x;
		}
		fa[c[x][fl^1]] = 1;
		c[y][fl] = c[x][fl^1];
		fa[y] = x; c[x][fl^1] = y;
		pushup(y); pushup(x); 
	}
	void splay(int x){
		int top = 0,now = x;
		st[++top] = x;
		while(!isroot(now)){
			st[++top] = (now = fa[now]);
		} 
		while(top){
			pushdown(st[top--]);
		}
		while(!isroot(x)){
			int y = fa[x], z = fa[y];
			if(!isroot(y)){
				if((c[y][1]==x) ^ (c[z][1]==y)){
					rotate(x);
				}else {
					rotate(y);
				}
			}
			rotate(x);
		}
	}
	void access(int x){
		for(int y=0;x;y=x,x=fa[y]){
			splay(x);
			c[x][1] = y;
			pushup(x);
		}
	}
	void makeroot(int x){
		access(x);
		splay(x);
		tag[x] ^= 1;
		pushdown(x);
	}
	int find(int x){
		access(x);
		splay(x);
		pushdown(x);
		while(c[x][0]){
			pushdown(x = c[x][0]);
		}
		return x;
	}
	void split(int x,int y){
		makeroot(x);
		access(y);
		splay(y);
	}
	void link(int x,int y){
		makeroot(x);
		fa[x] = y;
	}
	void cut(int x,int y){
		makeroot(x);
		fa[x] = c[y][0] = 0;
		pushup(y);
	}
}t;

signed main(){
	n=read(); m=read();
	int u,v;
	for(int i=1;i<n;i++){
		u=read(); v=read();
		t.link(u,v);
	}
	for(int i=1;i<=n;i++){
		mul[i] = w[i] = 1;
	}
	char opt;
	int a,b,c,d;
	while(m--){
		cin>>opt;
		if(opt == '+'){
			a=read(); b=read(); c=read();
			t.split(a,b);
			t.pusha(b,c);
		}
		if(opt == '-'){
			a=read(); b=read(); c=read(); d=read();
			if(t.find(a) == t.find(b)){
				t.cut(a,b);
			}
			if(t.find(c) != t.find(d)){
				t.link(c,d);
			}
		}
		if(opt == '*'){
			a=read(); b=read(); c=read();
			t.split(a,b);
			t.pushm(b,c);
		}
		if(opt == '/'){
			a=read(); b=read();
			t.split(a,b);
			printf("%d\n",val[b]%mod);
		}
	}
	return 0;
}