~~wow,完全看不懂……~~
有木有dalao解释解释？
by snowfox_chan @ 2020-04-29 21:45:32
大概所有人的 lct 写法都不太一样。。。所以自己调吧…反正就线段树2那种写法
by 1saunoya @ 2020-04-29 21:56:47
@[_Wallace_](/user/61430) 您错在哪里啊，我也0pts没调出来/kk
by UltiMadow @ 2020-04-29 23:04:22
@[UltiMadow](/user/65681) 发现rotate写错了
AC Code:
```cpp
/********************
Luogu P1501 [国家集训队]Tree II
https://www.luogu.com.cn/problem/P1501
********************/
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long llint;
const int N = 1e5 + 5;
const int mod = 51061;
#define lc ch[x][0]
#define rc ch[x][1]
int ch[N][2], size[N], fa[N];
llint val[N], sum[N], add[N], mul[N];
bool rev[N];
inline void pushup(int x) {
size[x] = size[lc] + size[rc] + 1;
sum[x] = (sum[lc] + sum[rc] + val[x]) % mod;
}
inline bool isRoot(int x) {
return x != ch[fa[x]][0] && x != ch[fa[x]][1];
}
inline void setRev(int x) {
swap(lc, rc), rev[x] ^= 1;
}
inline void setAdd(int x, int v) {
(add[x] += v) %= mod;
(val[x] += v) %= mod;
(sum[x] += llint(size[x]) * v % mod) %= mod;
}
inline void setMul(int x, int v) {
(add[x] *= v) %= mod;
(val[x] *= v) %= mod;
(sum[x] *= v) %= mod;
(mul[x] *= v) %= mod;
}
inline void pushdown(int x) {
if (mul[x] != 1) setMul(lc, mul[x]), setMul(rc, mul[x]);
if (add[x]) setAdd(lc, add[x]), setAdd(rc, add[x]);
if (rev[x]) { if (lc) setRev(lc); if (rc) setRev(rc); }
mul[x] = 1, rev[x] = add[x] = 0;
}
inline void rotate(int x) {
int y = fa[x], z = fa[y];
int k = ch[y][1] == x, w = ch[x][!k];
if (!isRoot(y)) ch[z][ch[z][1] == y] = x;
ch[x][!k] = y, ch[y][k] = w;
if (w) fa[w] = y;
fa[y] = x, fa[x] = z;
pushup(y);
}
inline int getch(int x) {
return x == ch[fa[x]][1];
}
int stk[N], top = 0;
void pushdownAll(int x) {
int y = x; stk[top = 1] = y;
while (!isRoot(y)) stk[++top] = y = fa[y];
while (top) pushdown(stk[top--]);
}
inline void splay(int x) {
pushdownAll(x);
for (register int y = fa[x]; !isRoot(x); rotate(x), y = fa[x])
if (!isRoot(y)) rotate(getch(x) != getch(y) ? x : y);
pushup(x);
}
inline void access(int x) {
for (register int y = 0; x; x = fa[y = x])
splay(x), rc = y, pushup(x);
}
inline void makeRoot(int x) {
access(x), splay(x), setRev(x);
}
inline void split(int x, int y) {
makeRoot(x), access(y), splay(y);
}
inline int findRoot(int x) {
access(x), splay(x), pushdown(x);
while(lc) pushdown(x = lc);
return splay(x), x;
}
inline void link(int x, int y) {
if (makeRoot(x), findRoot(y) != x) fa[x] = y;
}
inline void cut(int x, int y) {
makeRoot(x);
if (findRoot(y) == x && fa[y] == x && !ch[y][0])
fa[y] = rc = 0, pushup(x);
}
signed main() {
ios::sync_with_stdio(false);
int n, q;
cin >> n >> q;
for (register int i = 1; i <= n; i++)
mul[i] = val[i] = size[i] = sum[i] = 1;
for (register int i = 1, u, v; i < n; i++)
cin >> u >> v, link(u, v);
for (; q; --q) {
char cmd; int u, v, t;
cin >> cmd >> u >> v;
switch (cmd) {
case '+' : cin >> t, split(u, v), setAdd(v, t); break;
case '-' : cut(u, v), cin >> u >> v, link(u, v); break;
case '*' : cin >> t, split(u, v), setMul(v, t); break;
case '/' : split(u, v), cout << sum[v] << endl; break;
}
}
return 0;
}
```
by Lice @ 2020-04-29 23:06:25
@[_Wallace_](/user/61430) 蟹蟹，我自己再调一下（昨天睡觉了）
by UltiMadow @ 2020-04-30 08:13:31