Link-Cut-Tree 学习笔记
简介
LCT 是一种解决动态树问题的数据结构，是在虚实链剖分的基础上Splay维护。
类似Splay，只要掌握一些基本操作即可。
维护树链信息
P1501 [国家集训队]Tree II
题目描述
一棵
对于这棵树有
-
+ u v c：将u 到v 的路径上的点的权值都加上自然数c ； -
- u1 v1 u2 v2：将树中原有的边(u_1,v_1) 删除，加入一条新边(u_2,v_2) ，保证操作完之后仍然是一棵树； -
* u v c：将u 到v 的路径上的点的权值都乘上自然数c ； -
/ u v：询问u 到v 的路径上的点的权值和，将答案对51061 取模。
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
int x = 0, f = 1; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -f; c = getchar();}
while (c >= '0' && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
return x * f;
}
const int N = 2e5 + 10, mod = 51061;
int n, Q;
namespace LinkCutTree {
int fa[N], siz[N], ch[N][2], val[N], add[N], mul[N], rev[N], sum[N];
inline bool get(int x) {return x == ch[fa[x]][1];}
inline bool isRoot(int x) {return !fa[x] || ch[fa[x]][0] != x && ch[fa[x]][1] != x;}
inline void maintain(int x) {
siz[x] = (siz[ch[x][0]] + siz[ch[x][1]] + 1) % mod;
sum[x] = (sum[ch[x][0]] + sum[ch[x][1]] + val[x]) % mod;
}
inline void Mul(int x, int v) {(mul[x] *= v) %= mod; (val[x] *= v) %= mod; (sum[x] *= v) %= mod; (add[x] *= v) %= mod;}
inline void Add(int x, int v) {(val[x] += v) %= mod; (sum[x] += v * siz[x] % mod) %= mod; (add[x] += v) %= mod;}
inline void Reverse(int x) {rev[x] ^= 1; swap(ch[x][0], ch[x][1]);}
inline void pushdown(int x) {
if (mul[x] != 1) {
if (ch[x][0]) Mul(ch[x][0], mul[x]);
if (ch[x][1]) Mul(ch[x][1], mul[x]);
mul[x] = 1;
}
if (add[x]) {
if (ch[x][0]) Add(ch[x][0], add[x]);
if (ch[x][1]) Add(ch[x][1], add[x]);
add[x] = 0;
}
if (rev[x]) {
if (ch[x][0]) Reverse(ch[x][0]);
if (ch[x][1]) Reverse(ch[x][1]);
rev[x] = 0;
}
}
inline void Rotate(int x) {
int y = fa[x], z = fa[y], chk = get(x), w = ch[x][chk^1];
ch[y][chk] = w; if (w) fa[w] = y;
if (z && !isRoot(y)) ch[z][get(y)] = x; fa[x] = z;
ch[x][chk^1] = y; fa[y] = x;
maintain(y); maintain(x);
}
int q[N], qr;
inline void Splay(int x) {
q[qr = 0] = x;
for (int y = x; !isRoot(y); y = fa[y]) q[++qr] = fa[y];
for (int i = qr; ~i; -- i) pushdown(q[i]);
while (!isRoot(x)) {
if (!isRoot(fa[x]))
Rotate(get(x) == get(fa[x]) ? fa[x] : x);
Rotate(x);
}
}
inline void access(int x) {
for (int y = 0; x; y = x, x = fa[x]) {
Splay(x); ch[x][1] = y; maintain(x);
if (y) fa[y] = x;
}
}
inline int findRoot(int x) {
access(x); Splay(x);
while (ch[x][0]) pushdown(x), x = ch[x][0];
Splay(x); return x;
}
inline void makeRoot(int x) {access(x); Splay(x); Reverse(x);}
inline void Split(int x, int y) {makeRoot(x); access(y); Splay(y);}
inline void Link(int x, int y) {makeRoot(x); if (findRoot(x) != findRoot(y)) fa[x] = y;}
inline void Cut(int x, int y) {
makeRoot(x);
if (findRoot(x) != findRoot(y) || fa[y] != x || ch[y][0]) return;
fa[y] = ch[x][1] = 0;
assert(x);
maintain(x);
}
}
using namespace LinkCutTree;
signed main () {
n = read(); Q = read();
for (int i = 1; i <= n; ++ i) val[i] = 1, maintain(i);
for (int i = 1; i < n; ++ i) Link(read(), read());
while (Q --) {
char opt; scanf(" %c", &opt); int u = read(), v = read();
if (opt == '+') {
int c = read(); Split(u, v);
(val[v] += c) %= mod; (sum[v] += siz[v] * c % mod) % mod; (add[v] += c) %= mod;
}
if (opt == '-') {Cut(u, v); Link(read(), read());}
if (opt == '*') {
int c = read(); Split(u, v);
(val[v] *= c) %= mod; (sum[v] *= c) %= mod; (mul[v] *= c) %= mod;
}
if (opt == '/') {Split(u, v); printf("%lld\n", sum[v]);}
}
return 0;
}
类似题:
P3690 【模板】动态树（Link Cut Tree）\ P4332 [SHOI2014] 三叉神经树
维护联通信息
P2147 [SDOI2008] 洞穴勘测
判断连通性即可
Code
#include<bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0, f = 1; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -f; c = getchar();}
while (c >= '0' && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
return x * f;
}
const int N = 1e4 + 10;
int n, m;
namespace LinkCutTree {
int fa[N], lc[N], rc[N], rev[N];
inline int get(int x) {return rc[fa[x]] == x;}
inline bool isRoot(int x) {return !fa[x] || (lc[fa[x]] != x && rc[fa[x]] != x);}
inline void pushdown(int x) {
if (rev[x]) {
swap(lc[x], rc[x]);
if (lc[x]) rev[lc[x]] ^= 1;
if (rc[x]) rev[rc[x]] ^= 1;
rev[x] = 0;
}
}
inline void Rotate(int x) {
int y = fa[x], z = fa[y], b = lc[y] == x ? rc[x] : lc[x];
if (z && !isRoot(y)) (lc[z] == y ? lc[z] : rc[z]) = x;
fa[x] = z; fa[y] = x; b ? fa[b] = y : 0;
if (lc[y] == x) rc[x] = y, lc[y] = b;
else lc[x] = y, rc[y] = b;
}
int q[N], qr;
inline void Splay(int x) {
q[qr = 0] = x;
for (int y = x; !isRoot(y); y = fa[y]) q[++qr] = fa[y];
for (int i = qr; ~i; -- i) pushdown(q[i]);
while (!isRoot(x)) {
if (!isRoot(fa[x]))
Rotate(get(fa[x]) == get(x) ? fa[x] : x);
Rotate(x);
}
}
inline void access(int x) {
for (int y = 0; x; y = x, x = fa[x]) {
Splay(x); rc[x] = y;
if (y) fa[y] = x;
}
}
inline int findRoot(int x) {
access(x); Splay(x);
while (pushdown(x), lc[x]) x = lc[x];
Splay(x); return x;
}
inline void makeRoot(int x) {access(x); Splay(x); rev[x] ^= 1;}
inline void Link(int x, int y) {makeRoot(x); fa[x] = y;}
inline void Cut(int x, int y) {makeRoot(x); access(y); Splay(y); lc[y] = 0; fa[x] = 0;}
}
using namespace LinkCutTree;
int main () {
n = read(); m = read();
for (int i = 1; i <= m; ++ i) {
char opt[15];
scanf("%s", opt + 1);
if (opt[1] == 'Q') puts(findRoot(read()) == findRoot(read()) ? "Yes" : "No");
if (opt[1] == 'C') Link(read(), read());
if (opt[1] == 'D') Cut(read(), read());
}
return 0;
}
P2542 [AHOI2005] 航线规划
边转点，维护有效边
Code
#include<bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0, f = 1; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -f; c = getchar();}
while (c >= '0' && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
return x * f;
}
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
const int N = 2e5 + 10;
int n, m, Q, ans[N], from[N], to[N], id[N], opt[N];
struct Edge {int u, v, flg;} E[N];
map<Pair, int> mp;
namespace LinkCutTree {
int fa[N], ch[N][2], val[N], rev[N], tag[N], w[N];
inline bool get(int x) {return x == ch[fa[x]][1];}
inline bool isRoot(int x) {return !fa[x] || ch[fa[x]][0] != x && ch[fa[x]][1] != x;}
inline void maintain(int x) {val[x] = val[ch[x][0]] + val[ch[x][1]] + w[x];}
inline void modify(int x) {if (!x) return; w[x] = val[x] = 0; tag[x] = 1;}
inline void Reverse(int x) {if (!x) return; rev[x] ^= 1; swap(ch[x][0], ch[x][1]);}
inline void downdata(int x) {
if (tag[x]) tag[x] = 0, modify(ch[x][0]), modify(ch[x][1]), val[x] = 0;
if (rev[x]) Reverse(ch[x][0]), Reverse(ch[x][1]), rev[x] = 0;
}
inline void Rotate(int x) {
int y = fa[x], z = fa[y], chk = get(x), w = ch[x][chk ^ 1];
ch[y][chk] = w; if (w) fa[w] = y;
if (z && !isRoot(y)) ch[z][get(y)] = x; fa[x] = z;
ch[x][chk^1] = y; fa[y] = x;
maintain(y); maintain(x);
}
int q[N], qr;
inline void Splay(int x) {
q[qr = 0] = x;
for (int y = x; !isRoot(y); y = fa[y]) q[++qr] = fa[y];
for (int i = qr; ~i; --i) downdata(q[i]);
while (!isRoot(x)) {
if (!isRoot(fa[x]))
Rotate(get(x) == get(fa[x]) ? fa[x] : x);
Rotate(x);
}
}
inline void access(int x) {
for (int y = 0; x; y = x, x = fa[x]) {
Splay(x); ch[x][1] = y; maintain(x);
if (y) fa[y] = x;
}
}
inline void makeRoot(int x) {access(x); Splay(x); Reverse(x);}
inline int findRoot(int x) {
access(x); Splay(x);
while (downdata(x), ch[x][0]) x = ch[x][0];
Splay(x); return x;
}
inline void Split(int x, int y) {makeRoot(x); access(y); Splay(y);}
inline void Link(int x, int y) {makeRoot(x); if (findRoot(y) != x) fa[x] = y;}
inline void Cut(int x, int y) {
makeRoot(x);
if (findRoot(x) != findRoot(y) || fa[y] != x || ch[y][0]) return;
ch[x][1] = fa[y] = 0; maintain(x);
}
}
using namespace LinkCutTree;
int main () {
n = read(); m = read();
for (int i = 1; i <= m; ++ i) {
E[i] = (Edge) {read(), read(), 0};
if (E[i].u > E[i].v) swap(E[i].u, E[i].v);
mp[MP(E[i].u, E[i].v)] = i; w[i + n] = 1;
}
while (1) {
opt[++ Q] = read(); if (opt[Q] == -1) break;
from[Q] = read(); to[Q] = read();
if (from[Q] > to[Q]) swap(from[Q], to[Q]);
if (!opt[Q]) id[Q] = mp[MP(from[Q], to[Q])], E[id[Q]].flg = 1;
}
for (int i = 1; i <= m; ++ i) {
if (!E[i].flg) {
int u = E[i].u, v = E[i].v;
if (findRoot(u) == findRoot(v)) Split(u, v), modify(v);
else Link(u, i + n), Link(i + n, v);
}
}
// exit(0);
for (int i = Q-1; i >= 1; -- i) {
int u = from[i], v = to[i];
if (!opt[i]) {
if (findRoot(u) == findRoot(v)) Split(u, v), modify(v);
else Link(u, id[i] + n), Link(id[i] + n, v);
} else { Split(u, v); ans[i] = val[v];}
}
for (int i = 1; i < Q; ++ i)
if (opt[i]) printf("%d\n", ans[i]);
return 0;
}
bzoj 2959 长跑
两个并查集维护，一个维护无向图连通块，一个维护边双连通分量
Code
#include<bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0, f = 1; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -f; c = getchar();}
while (c >= '0' && c <= '9') {x = (x << 3) + (x << 1) + (c ^ 48); c = getchar();}
return x * f;
}
const int N = 3e5 + 10;
int n, m, val[N];
namespace Union {
int f[N], g[N];
inline int findF(int x) {return f[x] == x ? x : f[x] = findF(f[x]);}
inline int findG(int x) {return g[x] == x ? x : g[x] = findG(g[x]);}
}
using namespace Union;
namespace LinkCutTree {
int fa[N], tval[N], sum[N], rev[N], ch[N][2];
inline bool get(int x) {return x == ch[fa[x]][1];}
inline bool isRoot(int x) {return !fa[x] || ch[fa[x]][0] != x && ch[fa[x]][1] != x;}
inline void maintain(int x) {sum[x] = sum[ch[x][0]] + sum[ch[x][1]] + tval[x];}
inline void Reverse(int x) {swap(ch[x][0], ch[x][1]); rev[x] ^= 1;}
inline void downdata(int x) {
if (rev[x]) {
if (ch[x][0]) Reverse(ch[x][0]);
if (ch[x][1]) Reverse(ch[x][1]);
rev[x] = 0;
}
}
inline void Rotate(int x) {
int y = fa[x], z = fa[y], chk = get(x), w = ch[x][chk ^ 1];
ch[y][chk] = w; if (w) fa[w] = y;
if (z && !isRoot(y)) ch[z][get(y)] = x; fa[x] = z;
ch[x][chk ^ 1] = y; fa[y] = x;
maintain(y); maintain(x);
}
int q[N], qr;
inline void Splay(int x) {
q[qr = 0] = x;
for (int y = x; !isRoot(y); y = fa[y]) q[++qr] = fa[y];
for (int i = qr; ~i; -- i) downdata(q[i]);
while (!isRoot(x)) {
if (!isRoot(fa[x]))
Rotate(get(x) == get(fa[x]) ? fa[x] : x);
Rotate(x);
}
}
inline void access(int x) {
for (int y = 0; x; y = x, x = findF(fa[x])) {
Splay(x); ch[x][1] = y; maintain(x);
if (y) fa[y] = x;
}
}
inline void makeRoot(int x) {access(x); Splay(x); Reverse(x);}
inline void Split(int x, int y) {makeRoot(x); access(y); Splay(y);}
inline void Link(int x, int y) {makeRoot(x); fa[x] = y;}
inline void dfs(int x, int rt) {
f[x] = rt;
if (ch[x][0]) dfs(ch[x][0], rt);
if (ch[x][1]) dfs(ch[x][1], rt);
}
}
using namespace LinkCutTree;
int main () {
n = read(); m = read();
for (int i = 1; i <= n; ++ i) {val[i] = read(); tval[i] = sum[i] = val[i]; f[i] = g[i] = i;}
while (m --) {
int opt = read(), x = read(), y = read();
int fx = findF(x), fy = findF(y);
if (opt == 1) {
if (fx != fy) {
if (findG(fx) != findG(fy)) {
Link(fx, fy); g[g[fx]] = g[fy];
} else {
Split(fx, fy); tval[fy] = sum[fy];
dfs(fy, fy); ch[fy][0] = 0;
}
}
}
if (opt == 2) { Splay(fx); tval[fx] += y - val[x]; sum[fx] += y - val[x]; val[x] = y;}
if (opt == 3) {
if (findG(fx) != findG(fy)) puts("-1");
else {Split(fx, fy); printf("%d\n", sum[fy]);}
}
}
return 0;
}