```
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define int long long
#define maxn 200010
#define wzx 51061
#define re register
#define FOR(i, l, r) for(re int i = l; i <= r; ++i)
using namespace std;
int n, m, c, r, t, x, y, z, k;
int a[maxn], b[maxn], tagv[maxn], taga[maxn], tagm[maxn], ans[maxn], son[maxn][2], fa[maxn], siz[maxn];
int ifr(int x) {
return x == son[fa[x]][1];
}
int nrt(int x) {
return x == son[fa[x]][0] || x == son[fa[x]][1];
}
void push_up(int x) {
ans[x] = (ans[son[x][0]] + ans[son[x][1]] + a[x])%wzx;
siz[x] = siz[son[x][0]] + siz[son[x][1]] + 1;
}
void push_mul(int x, int k) {
ans[x] = ans[x]*k%wzx;
a[x] = a[x]*k%wzx;
tagm[x] = tagm[x]*k%wzx;
taga[x] = taga[x]*k%wzx;
}
void push_add(int x, int k) {
ans[x] = (ans[x]+siz[x]*k)%wzx;
a[x] = (a[x]+k)%wzx;
taga[x] = (taga[x]+k)%wzx;
}
void phr(int x) {
swap(son[x][0], son[x][1]);
tagv[x] ^= 1;
}
void push_down(int x) {
if(tagm[x] != 1) {
push_mul(son[x][0], tagm[x]);
push_mul(son[x][1], tagm[x]);
tagm[x] = 1;
}
if(taga[x]) {
push_add(son[x][0], taga[x]);
push_add(son[x][1], taga[x]);
taga[x] = 0;
}
if(tagv[x]) {
phr(son[x][0]);
phr(son[x][1]);
tagv[x] = 0;
}
}
void rotate(int x) {
int f = fa[x], ff = fa[f], pd1 = ifr(x), pd2 = ifr(f), t = son[x][pd1^1];
if(nrt(f))
son[ff][pd2] = x;
son[x][pd1^1] = f;
son[f][pd1] = t;
if(t)
fa[t] = f;
fa[f] = x;
fa[x] = ff;
push_up(f);
push_up(x);
}
void splay(int x) {
int f = x;
b[++b[0]] = f;
while(nrt(f))
b[++b[0]] = f = fa[f];
while(b[0])
push_down(b[b[0]--]);
while(nrt(x)) {
f = fa[x];
if(nrt(f))
rotate(ifr(f) == ifr(x) ? f : x);
rotate(x);
}
push_up(x);
}
void access(int x) {
for(re int f = 0; x; x = fa[f = x])
splay(x), son[x][1] = f, push_up(x);
}
void makeroot(int x) {
access(x);
splay(x);
phr(x);
}
int findroot(int x) {
access(x);
splay(x);
while(son[x][0])
push_down(x), x = son[x][0];
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(findroot(y) != x) //就是这个地方啊qwqwq
fa[x] = y;
}
void cut(int x, int y) {
makeroot(x);
if(findroot(y) == x && fa[y] == x && !son[y][0]) {
fa[y] = son[x][1] = 0;
push_up(x);
}
}
signed main() {
scanf("%lld%lld", &n, &m);
FOR(i, 1, n-1) {
scanf("%lld%lld", &x, &y);
link(x, y);
}
FOR(i, 1, n)
a[i] = siz[i] = tagm[i] = 1;
char ch;
FOR(i, 1, m) {
cin >> ch;
if(ch == '+') {
scanf("%lld%lld%lld", &x, &y, &k);
split(x, y);
push_add(y, k);
}
if(ch == '-') {
scanf("%lld%lld%lld%lld", &x, &y, &z, &k);
cut(x, y);
link(z, k);
}
if(ch == '*') {
scanf("%lld%lld%lld", &x, &y, &k);
split(x, y);
push_mul(y, k);
}
if(ch == '/') {
scanf("%lld%lld", &x, &y);
split(x, y);
printf("%lld\n", ans[y]);
}
}
}
```
by Juan_feng @ 2019-02-14 07:55:49
Orz 萌新学LCT
by YLWang @ 2019-02-14 08:11:26
%%%%%%%%
by RiverFun @ 2019-02-14 08:21:59