RT

WA #1、#20，MLE #12~19，50pts

record

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

const unsigned int MOD = 51061;

const unsigned int MAXN = 1e5 + 10;

struct Link_Cut_Tree {
    unsigned int Son[MAXN][2], Fa[MAXN];
    unsigned int Value[MAXN];
    unsigned int Tag_Mu[MAXN], Tag_Add[MAXN];
    unsigned int Size[MAXN], Sum[MAXN];
    bool Tag_Reverse[MAXN];

    bool IsRoot(int x) {
        return Son[Fa[x]][0] != x && Son[Fa[x]][1] != x;
    }

    int Get(int x) {
        return Son[Fa[x]][1] == x;
    }

    void PushUp(int x) {
        Sum[x] = (Sum[Son[x][0]] + Sum[Son[x][1]] + Value[x]) % MOD;
        Size[x] = (Size[Son[x][0]] + Size[Son[x][1]] + 1) % MOD;
        return;
    }

    void PushDown(int x) {
        if (Tag_Reverse[x]) {
            if (Son[x][0]) Tag_Reverse[Son[x][0]] ^= 1, swap(Son[Son[x][0]][0], Son[Son[x][0]][1]);
            if (Son[x][1]) Tag_Reverse[Son[x][1]] ^= 1, swap(Son[Son[x][1]][0], Son[Son[x][1]][1]);

            Tag_Reverse[x] ^= 1;
        }

        if (Tag_Mu[x] != 1) {
            if (Son[x][0]) {
                Tag_Mu[Son[x][0]] = (Tag_Mu[Son[x][0]] * Tag_Mu[x]) % MOD;
                Value[Son[x][0]] = (Value[Son[x][0]] * Tag_Mu[x]) % MOD;
                Tag_Add[Son[x][0]] = (Tag_Add[Son[x][0]] * Tag_Mu[x]) % MOD;
                Sum[Son[x][0]] = (Sum[Son[x][0]] * Tag_Mu[x]) % MOD;
            }

            if (Son[x][1]) {
                Tag_Mu[Son[x][1]] = (Tag_Mu[Son[x][1]] * Tag_Mu[x]) % MOD;
                Value[Son[x][1]] = (Value[Son[x][1]] * Tag_Mu[x]) % MOD;
                Tag_Add[Son[x][1]] = (Tag_Add[Son[x][1]] * Tag_Mu[x]) % MOD;
                Sum[Son[x][1]] = (Sum[Son[x][1]] * Tag_Mu[x]) % MOD;
            }

            Tag_Mu[x] = 1;
        }

        if (Tag_Add[x]) {
            if (Son[x][0]) {
                Value[Son[x][0]] = (Value[Son[x][0]] + Tag_Add[x]) % MOD;
                Tag_Add[Son[x][0]] = (Tag_Add[Son[x][0]] + Tag_Add[x]) % MOD;
                Sum[Son[x][0]] = (Sum[Son[x][0]] + Tag_Add[x] * Size[Son[x][0]] % MOD) % MOD;
            }

            if (Son[x][1]) {
                Value[Son[x][1]] = (Value[Son[x][1]] + Tag_Add[x]) % MOD;
                Tag_Add[Son[x][1]] = (Tag_Add[Son[x][1]] + Tag_Add[x]) % MOD;
                Sum[Son[x][1]] = (Sum[Son[x][1]] + Tag_Add[x] * Size[Son[x][1]] % MOD) % MOD;
            }

            Tag_Add[x] = 0;
        }
    }

    void UpDate(int x) {
        if (!IsRoot(x)) UpDate(Fa[x]);
        PushDown(x);
    }

    void Rotate(int x) {
        int y = Fa[x], z = Fa[y], k = Get(x);
        if (!IsRoot(y)) Son[z][Son[z][1] == y] = x;
        Son[y][k] = Son[x][!k];
        Fa[Son[x][!k]] = y;
        Son[x][!k] = y;
        Fa[y] = x;
        Fa[x] = z;
        PushUp(y);
        PushUp(x);
        return;
    }

    void Splay(int x) {
        UpDate(x);
        for (int fa = Fa[x]; fa = Fa[x], !IsRoot(x); Rotate(x)) {
            if (!IsRoot(fa)) Rotate(Get(fa) == Get(x) ? fa : x);
        }
    }

    int Access(int x) {
        int p = 0;
        for (p = 0; x; p = x, x = Fa[x]) {
            Splay(x);
            Son[x][1] = p;
            PushUp(x);
        }

        return p;
    }

    int Find(int p) {
        Access(p);
        Splay(p);
        while (Son[p][0]) {
        	PushDown(p);
            p = Son[p][0];
        }
        Splay(p);
        return p;
    }

    void MakeRoot(int x) {
        Access(x);
        Splay(x);
        Tag_Reverse[x] ^= 1;
        swap(Son[x][0], Son[x][1]);
    }

    void Link(int x, int y) {
        if (Find(x) == Find(y)) return;
        MakeRoot(x);
        Fa[x] = y;
    }

    void Split(int x, int y) {
        MakeRoot(x);
        Access(y);
        Splay(y);
    }

    void Cut(int x, int y) {
        if (Find(x) != Find(y)) return;
        Split(x, y);
        if (Son[y][Get(x) ^ 1] || Fa[x] != y || Son[x][1]) return;
        Fa[x] = Son[x][0] = 0;
        PushUp(y);
    }
} LCT;

int N, Q;

char Op;
unsigned int u, v, c;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

	cin >> N >> Q;
	
	for (int i = 1; i <= N; i++) {
    	LCT.Value[i] = LCT.Tag_Mu[i] = 1;
    	LCT.PushUp(i);
	}
	
    for (int i = 1, u, v; i < N; i++) {
        cin >> u >> v;
        
        LCT.Link(u, v);
    }
    
    while (Q--) {
    	cin >> Op;
        if (Op == '+') {
            cin >> u >> v >> c;

            LCT.Split(u, v);

            LCT.Tag_Add[v] = (LCT.Tag_Add[v] + c) % MOD;
            LCT.Value[v] = (LCT.Value[v] + c) % MOD;
            LCT.Sum[v] = (LCT.Sum[v] + c * LCT.Size[v] % MOD) % MOD;
        }
    
	    if (Op == '-') {
	    	cin >> u >> v;
	    	
	    	LCT.Cut(u, v);
	    	
	    	cin >> u >> v;
	    	
	    	LCT.Link(u, v);
		}
		
		if (Op == '*') {
			cin >> u >> v >> c;
	
	        LCT.Split(u, v);
			
			LCT.Value[v] = LCT.Value[v] * c % MOD;
			LCT.Sum[v] = LCT.Sum[v] * c % MOD;
			LCT.Tag_Mu[v] = LCT.Tag_Mu[v] * c % MOD;
		}
		
		if (Op == '/') {
			cin >> u >> v;
			
			LCT.Split(u, v);
			cout << LCT.Sum[v] << endl;
		}
	}
    return 0;
}