# 自闭啦QAQ

@_Wallace_  2020-04-29 21:43 回复

#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];
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) {
(val[x] += v) %= mod;
(sum[x] += llint(size[x]) * v % mod) %= mod;
}
inline void setMul(int x, int v) {
(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 (rev[x]) {
if (lc) setRev(lc);
if (rc) setRev(rc);
}
mul[x] = 1, rev[x] = add[x] = 0;
}

inline int getch(int x) {
return x == ch[fa[x]][1];
}
inline void connect(int x, int f, int c) {
fa[x] = f, ch[f][c] =x;
}
inline void rotate(int x) {
int y = fa[x], r = fa[y];
int u = getch(x), v = getch(y);
int b = ch[x][u ^ 1];
fa[x] = r;
if (!isRoot(y)) connect(x, r, v);
connect(b, y, u), connect(y, x, u ^ 1);
pushup(y), pushup(x), pushup(r);
}

void pushdownAll(int x) {
if (!isRoot(x)) pushdownAll(fa[x]);
pushdown(x);
}
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] = 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;
}

@Isaunoya 2020-04-29 21:56 回复 举报

@_Wallace_  2020-04-29 23:06 回复 举报

AC Code:

/********************
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];
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) {
(val[x] += v) %= mod;
(sum[x] += llint(size[x]) * v % mod) %= mod;
}
inline void setMul(int x, int v) {
(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 (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;
}