# 萌新求助，本地能过，你谷MLE。

@too_late 2020-10-16 19:31 回复

#include <bits/stdc++.h>
#define I inline
#define int long long
#define RI register int
#define ls ch[p][0]
#define rs ch[p][1]
#define N 100005
#define mo 51061
using namespace std;

class LCT{
public:
int top, st[N], f[N], ch[N][2], val[N], add[N], mul[N], sum[N], sz[N], tag[N];
I int up(int p){ sz[p] = sz[ls] + sz[rs] + 1, sum[p] = (sum[ls] + sum[rs] + val[p]) % mo; }
I void down(int p){
if(tag[p]){ ls ^= rs ^= ls ^= rs, tag[ls] ^= 1, tag[rs] ^= 1, tag[p] = 0; }
if(mu != 1){
mul[ls] = (mul[ls] * mu) % mo; mul[rs] = (mul[rs] * mu) % mo;
sum[ls] = (sum[ls] * mu) % mo; sum[rs] = (sum[rs] * mu) % mo;
val[ls] = (val[ls] * mu) % mo; val[rs] = (val[rs] * mu) % mo; mul[p] = 1;
sum[ls] = (sum[ls] + ad * sz[ls]) % mo; sum[rs] = (sum[rs] + ad * sz[rs]) % mo;
val[ls] = (val[ls] + ad) % mo; val[rs] = (val[rs] + ad) % mo; add[p] = 0;
}
}
I bool isroot(int p){ return p != ch[f[p]][0] && p != ch[f[p]][1]; }
I int get(int p){ return p == ch[f[p]][1]; }
I void rotate(int x){
int y = f[x], z = f[y], k = get(x); if(!isroot(y)) ch[z][ch[z][1] == y] = x;
ch[y][k] = ch[x][!k], f[ch[x][!k]] = y, ch[x][!k] = y, f[y] = x, f[x] = z, up(y), up(x);
}
I void splay(int x){
RI i,fa; st[top = 1] = i = x; while(!isroot(i)) st[++top] = i = f[i];
while(top) down(st[top--]); for(; fa = f[x], !isroot(x); rotate(x))
if(!isroot(fa)) rotate(get(fa) == get(x)? fa: x);
}void print(int p) { if (!p) return; down(p); print(ls); printf("%lld ", p); print(rs); }

I void access(int p){ RI q; for(q = 0; p; q = p, p = f[p]) splay(p), rs = q, up(p); }
I void makeroot(int p){ access(p), splay(p), tag[p] ^= 1; }
I int findroot(int p){ splay(p); while(ls) p = ls; return splay(p), p; }
I void split(int x, int y){ makeroot(x); access(y), splay(y); }
I void link(int x, int y){ makeroot(x); if(findroot(y) != x) f[x] = y; }
I void cut(int x, int y){ split(x, y); if(ch[y][0] == x) ch[y][0] = f[x] = 0; up(x); }
} tr;

int n, m, x, y, z, c;
char op[10];

signed main(){
RI i; for(i = 1; i < N; i++) tr.mul[i] = tr.val[i] = tr.sz[i] = 1; tr.val[0] = 0;
for(scanf("%d%d", &n, &m), i = 1; i < n; i++) scanf("%d%d", &x, &y), tr.link(x, y);
for(i = 1; i <= m; i++){ scanf("%s", op + 1);
for(int i = 1; i <= n; i++) tr.down(i);
if(op[1] == '+') scanf("%d%d%d", &x, &y, &z), tr.split(x, y), tr.val[y] = (tr.val[y] + z) % mo,
tr.sum[y] = (tr.sum[y] + z * tr.sz[y]) % mo, tr.add[y] = (tr.add[y] + z) % mo;
if(op[1] == '*') scanf("%d%d%d", &x, &y, &z), tr.split(x, y), tr.val[y] = (tr.val[y] * z) % mo,
tr.sum[y] = (tr.sum[y] * z) % mo, tr.mul[y] = (tr.mul[y] * z) % mo;
if(op[1] == '-') scanf("%d%d%d%d", &x, &y, &z, &c), tr.cut(x, y), tr.link(z, c);
if(op[1] == '/') scanf("%d%d", &x, &y), tr.split(x, y), printf("%d\n", tr.sum[y]);
}
exit(0);
}