Kruskal 重构树 学习笔记
一、概述
Kruskal 重构树(Kruskal Reconstruction Tree,KRT)是一种基于 Kruskal 最小/最大生成树算法构建的树形结构。它将原图中的边按权值排序后,通过并查集合并节点,每次合并时新建一个虚节点作为两个连通块的父节点,最终形成一棵二叉树(或多叉树)。
Kruskal 重构树的核心思想是:将边权信息转化为点权信息,从而利用树上的 LCA、倍增、子树查询等技巧高效解决原图的瓶颈路问题。
二、构建过程
2.1 算法步骤
- 初始化:原图有 $n$ 个节点,重构树初始有 $n$ 个叶节点(对应原图节点,权值设为 $-1$ 或无穷)。
- 排序:将边按权值排序。
- 若求最大瓶颈路(即路径上最大边权的最小值),则边按降序排序。
- 若求最小瓶颈路(即路径上最小边权的最大值),则边按升序排序。 - 合并:按顺序遍历每条边 $(u, v, w)$:
- 找到 $u$ 和 $v$ 所在连通块的根 $ru, rv$。
- 若 $ru = rv$,跳过。
- 新建一个虚节点 $node$,权值设为 $w$。
- 将 $ru$ 和 $rv$ 作为 $node$ 的两个子节点。
- 在并查集中将 $ru, rv, node$ 合并,$node$ 为新的根。 - 倍增预处理:构建完成后,进行 DFS 预处理深度和倍增表,用于快速 LCA 查询。
2.2 可视化示意
原图: 重构树:
1 4(虚节点, 权值=5)
/ \ / \
2---3---5 1 3(虚节点, 权值=3)
| / \
边权: 2 4 5
1-2:5
1-3:3
2-3:2
3-5:1
3-4:4
三、重要性质
设原图有 $n$ 个节点,重构树有 $2n-1$ 个节点(最坏情况)。以下性质以最大瓶颈路(降序构建)为例:
性质 1:堆性质(单调性)
重构树中,从叶节点到根的路径上,节点权值单调不增(降序构建)或单调不减(升序构建)。
- 降序构建:虚节点权值 = 边权,越往上边权越小,路径上权值递减。
- 升序构建:虚节点权值 = 边权,越往上边权越大,路径上权值递增。
性质 2:瓶颈路与 LCA
原图中任意两点 $u, v$ 之间所有路径中,最大边权的最小值(即最大瓶颈路)等于重构树上 $u$ 和 $v$ 的 LCA 的权值。
$$
\text{maxEdgeMin}(u, v) = \text{val}[\text{LCA}(u, v)]
$$
同理,升序构建时,LCA 权值就是最小边权的最大值(最小瓶颈路)。
性质 3:连通性与子树
对于原图中的一个节点 $s$,若限制只走边权 $\le \text{lim}$ 的边,则所有能到达的节点恰好是重构树上从 $s$ 向上跳到某个祖先 $x$(满足 $\text{val}[x] \le \text{lim}$ 且 $\text{val}[\text{parent}[x]] > \text{lim}$),然后 $x$ 的子树中所有叶节点(原图节点)。
这一性质使得在限制条件下查询可达节点集变得十分高效。
性质 4:二叉性
每合并一次新建一个虚节点,该虚节点恰好有两个子节点(即两个连通块的根)。因此重构树是一棵二叉树(但存储时可用邻接表作为多叉树,不影响)。
四、常见应用
4.1 瓶颈路查询
| 问题 | 排序方式 | 查询方法 |
|---|---|---|
| 最大边权的最小值 | 降序 | val[LCA(u,v)] |
| 最小边权的最大值 | 升序 | val[LCA(u,v)] |
4.2 限制边权下的可达节点
- 上限限制(只能走边权 $\le \text{lim}$ 的边):在降序构建的树上,从 $s$ 倍增跳到最浅的满足 $\text{val}[x] \le \text{lim}$ 的祖先,其子树中叶节点即为答案。
- 下限限制(只能走边权 $\ge \text{lim}$ 的边):在降序构建的树上,从 $s$ 倍增跳到最浅的满足 $\text{val}[x] \ge \text{lim}$ 的祖先,其子树中叶节点即为答案。
4.3 离线动态连通性
由于重构树保存了合并的历史,可以回答"在某时刻(边权阈值)两个点是否连通"的问题——只需判断在重构树上它们 LCA 的权值是否满足条件。
4.4 与树上问题结合
重构树是一棵树,可以叠加以下技巧:
- 树上差分:路径权值统计
- 树链剖分:支持路径修改/查询
- 可持久化线段树:在 DFS 序上处理子树问题
- 倍增/轻重链:快速跳祖先
五、模板代码解析
查看 KruskalReconstructionTree.cpp 中的实现:
核心成员
| 变量 | 含义 |
|---|---|
n |
原图节点数 |
tot |
重构树总节点数(从 $n$ 开始增长) |
g |
邻接表 |
val |
节点权值,原节点为 -1,虚节点为边权 |
parent |
父节点(用于倍增) |
dsu |
并查集 |
主要函数
| 函数 | 功能 |
|---|---|
build(edges, sorted) |
构建重构树,默认按降序(最大瓶颈路) |
lca(u, v) |
查询 LCA |
queryMaxEdgeMin(u, v) |
查询 $u \to v$ 最大瓶颈路 |
queryReachable(s, lim) |
从 $s$ 走边权 $\le \text{lim}$ 能到的所有点 |
queryReachableMin(s, lim) |
从 $s$ 走边权 $\ge \text{lim}$ 能到的所有点 |
注意事项
- 构建时预先
resize(2n),动态扩容逻辑保证越界安全。 - 倍增的
LOG取 20,适用于 $n \le 10^5$ 级别;若 $n$ 更大(如 $2 \times 10^5$),建议取 18–20,或按__lg(2*n)+1动态计算。 collectLeaves使用 DFS 递归收集子树中叶节点;若子树很大,可能需用迭代或剪枝优化。- 升序构建只需将排序比较器的
>改为<。
六、时间复杂度
| 步骤 | 复杂度 |
|---|---|
| 排序 | $O(m \log m)$ |
| 并查集合并 | $O(m \alpha(n))$ |
| 倍增预处理 DFS | $O(n \log n)$ |
| 单次 LCA 查询 | $O(\log n)$ |
| 单次可达节点查询 | $O(\log n + \text{答案大小})$ |
七、例题推荐
| 题目 | 来源 | 说明 |
|---|---|---|
| P1967 [NOIP2013 提高组] 货车运输 | NOIP | 最大瓶颈路(经典题) |
| P2245 星际导航 | 洛谷 | 瓶颈路模板 |
| CF1628C1 - K-Complete Word | Codeforces | 重构树可达性 |
| P4768 [NOI2018] 归程 | NOI | 重构树 + Dijkstra 预处理 |
| P4197 Peaks | 洛谷 | 重构树 + 可持久化线段树 |
| CF1706E - Qpwoeirut and Vertor | Codeforces | 多组询问瓶颈路 |
八、总结
Kruskal 重构树是一种极具巧思的数据结构,它将边权转化为点权,将原图的瓶颈问题转化为树上的 LCA 或子树问题。其核心优势在于:
- 在线查询:构建一次,多次回答任意两点间的瓶颈路。
- 限制可达性:通过倍增跳祖先,快速定位满足边权约束的子树。
- 易于扩展:可与树剖、可持久化、差分等树上技术无缝结合。
掌握它,你将能轻松解决一类"边权限制下的连通性与最值"问题。
附录:C++ 模板
/* Kruskal Reconstruction Tree Template */
/* 最大瓶颈路(降序构建),如需最小瓶颈路将排序改为升序 */
#include <bits/stdc++.h>
using namespace std;
struct KruskalReconstructionTree {
int n; // 原图节点数
int tot; // 重构树总节点数
vector<vector<int>> g; // 树邻接表
vector<int> val; // 节点权值 (原节点 -1)
vector<int> parent; // 父节点
vector<int> dsu; // 并查集
static const int LOG = 20; // 倍增 LCA 参数
vector<int> depth;
vector<vector<int>> up;
KruskalReconstructionTree(int n_) : n(n_) {
tot = n;
g.resize(2 * n);
val.resize(2 * n);
parent.assign(2 * n, -1);
dsu.resize(2 * n);
iota(dsu.begin(), dsu.end(), 0);
for (int i = 0; i < n; i++) val[i] = -1;
depth.resize(2 * n);
}
int find(int x) {
while (dsu[x] != x) dsu[x] = dsu[dsu[x]], x = dsu[x];
return x;
}
// 构建重构树。edges: {u,v,w}
void build(vector<tuple<int, int, int>> edges, bool sorted = false) {
if (!sorted) {
sort(edges.begin(), edges.end(),
[](const auto &a, const auto &b) {
return get<2>(a) > get<2>(b); // 最大瓶颈路
});
}
for (auto &[u, v, w] : edges) {
int ru = find(u), rv = find(v);
if (ru == rv) continue;
int node = tot++;
val[node] = w;
g[node].push_back(ru);
g[node].push_back(rv);
parent[ru] = parent[rv] = node;
dsu[ru] = dsu[rv] = node;
dsu[node] = node;
if (tot >= (int)g.size()) {
g.resize(tot + 5);
val.resize(tot + 5);
parent.resize(tot + 5);
depth.resize(tot + 5);
}
}
g.resize(tot);
val.resize(tot);
parent.resize(tot);
// 建立倍增表
initLCA();
}
void initLCA() {
depth.assign(tot, 0);
up.assign(tot, vector<int>(LOG, -1));
for (int i = 0; i < tot; i++)
if (parent[i] == -1) dfs(i, -1);
}
void dfs(int u, int p) {
up[u][0] = p;
for (int j = 1; j < LOG; j++) {
if (up[u][j - 1] != -1)
up[u][j] = up[up[u][j - 1]][j - 1];
else
up[u][j] = -1;
}
for (int v : g[u]) {
if (v == p) continue;
depth[v] = depth[u] + 1;
dfs(v, u);
}
}
// 查询 u, v 的 LCA
int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
for (int j = 0; j < LOG; j++) {
if (diff >> j & 1) u = up[u][j];
}
if (u == v) return u;
for (int j = LOG - 1; j >= 0; j--) {
if (up[u][j] != up[v][j]) {
u = up[u][j];
v = up[v][j];
}
}
return up[u][0];
}
// 查询原图 u->v 瓶颈路(最大边权的最小值)
int queryMaxEdgeMin(int u, int v) {
int w = lca(u, v);
if (w == -1) return -1;
return val[w];
}
// 从 s 出发,仅走边权 ≤ lim 的边能到达的所有节点
vector<int> queryReachable(int s, int lim) {
int u = s;
for (int j = LOG - 1; j >= 0; j--)
if (up[u][j] != -1 && val[up[u][j]] <= lim)
u = up[u][j];
vector<int> res;
collectLeaves(u, -1, res);
return res;
}
// 从 s 出发,仅走边权 ≥ lim 的边能到达的所有节点(需降序构建)
vector<int> queryReachableMin(int s, int lim) {
int u = s;
for (int j = LOG - 1; j >= 0; j--)
if (up[u][j] != -1 && val[up[u][j]] >= lim)
u = up[u][j];
vector<int> res;
collectLeaves(u, -1, res);
return res;
}
// 收集子树中所有原图节点
void collectLeaves(int u, int p, vector<int> &out) {
if (u < n) { out.push_back(u); return; }
for (int v : g[u]) if (v != p) collectLeaves(v, u, out);
}
};