[BZOJ2631][Tree][LCT]

题目大意：

给定一棵 N<=100000 个节点的无根树，有四种操作：删除一条边后再加一条边（保证形成的还是一棵树）、在树上的一条路径上全部加一个权值、在树上的一条路径上全部乘一个权值、求树上一条路径的权值和。

答案要 %51061

思路：

显然这棵树是动态的，那么用LCT来维护连通性就好了，加和乘的操作可以在splay里面打lazy标记来维护。

求树上的一条路径可以用split操作。

注意在access的时候对于每个经过的点都要pushup一遍。

代码：

#include <bits/stdc++.h> using namespace std; typedef unsigned int ll; const int Maxn = 100005; const int Mod = 51061; namespace IO { inline char get(void) { static char buf[1000000], *p1 = buf, *p2 = buf; if (p1 == p2) { p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin); if (p1 == p2) return EOF; } return *p1++; } inline void read(int &x) { x = 0; static char c; bool f = 0; for (; !(c >= '0' && c <= '9'); c = get()) if (c == '-') f = 1; for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = get()); if (f) x = -x; } inline void read(char &x) { x = get(); while (!(x == '*' || x == '/' || x == '+' || x == '-')) x = get(); } inline void write(int x) { if (!x) return (void)puts("0"); if (x < 0) putchar('-'), x = -x; static short s[12], t; while (x) s[++t] = x % 10, x /= 10; while (t) putchar('0' + s[t--]); putchar('\n'); } }; int fa[Maxn], c[Maxn][2], st[Maxn], top, size[Maxn], nxt[Maxn]; bool rev[Maxn]; ll mx[Maxn], at[Maxn], val[Maxn], sum[Maxn]; inline void cal(int x, int m, int a) { if (!x) return; val[x] = (val[x] * m + a) % Mod; sum[x] = (sum[x] * m + a * size[x]) % Mod; at[x] = (at[x] * m + a) % Mod; mx[x] = (mx[x] * m) % Mod; } inline bool isRt(int x) { return c[fa[x]][0] != x && c[fa[x]][1] != x; } inline void pushDown(int x) { static int l, r; l = c[x][0], r = c[x][1]; if (rev[x]) { rev[l] ^= 1; rev[r] ^= 1; swap(c[x][0], c[x][1]); rev[x] ^= 1; } int m = mx[x], a = at[x]; mx[x] = 1, at[x] = 0; if (m != 1 || a != 0) { cal(l, m, a), cal(r, m, a); } } inline void pushUp(int x) { int l = c[x][0], r = c[x][1]; sum[x] = (sum[l] + sum[r] + val[x]) % Mod; size[x] = (size[l] + size[r] + 1) % Mod;; } inline void rotate(int x) { int y = fa[x], z = fa[y], l, r; r = c[y][0] == x; l = r ^ 1; if (!isRt(y)) { if (c[z][0] == y) c[z][0] = x; else c[z][1] = x; } fa[x] = z; fa[y] = x; fa[c[x][r]] = y; c[y][l] = c[x][r]; c[x][r] = y; pushUp(y); pushUp(x); } inline void splay(int x) { st[top = 1] = x; for (int i = x; !isRt(i); i = fa[i]) st[++top] = fa[i]; while (top) pushDown(st[top--]); int y, z; while (!isRt(x)) { y = fa[x], z = fa[y]; if (!isRt(y)) { if (c[y][0] == x ^ c[z][0] == y) rotate(x); else rotate(y); } rotate(x); } } inline void access(int x) { int t = 0; while (x) { splay(x); c[x][1] = t; pushUp(x); t = x; x = fa[x]; } } inline void rever(int x) { access(x); splay(x); rev[x] ^= 1; } inline void link(int x, int y) { rever(x); fa[x] = y; // splay(x); } inline void cut(int x, int y) { rever(x); access(y); splay(y); c[y][0] = fa[x] = 0; } inline void split(int x, int y) { rever(y); access(x); splay(x); } int n, m; int main(void) { //freopen("in.txt", "r", stdin); IO::read(n), IO::read(m); for (int i = 1; i <= n; i++) val[i] = sum[i] = mx[i] = size[i] = 1; for (int i = 1, u, v; i < n; i++) { IO::read(u), IO::read(v); link(u, v); } char op; int u, v, c, d; for (int i = 1; i <= m; i++) { IO::read(op); IO::read(u), IO::read(v); if (op == '+') { IO::read(c); split(u, v); cal(u, 1, c); } else if (op == '-') { IO::read(c), IO::read(d); cut(u, v), link(c, d); } else if (op == '*') { IO::read(c); split(u, v), cal(u, c, 0); } else { split(u, v); IO::write(sum[u]); } } return 0; }

完。

By g1n0st