登录

Kruskal 重构树

Kruskal 重构树 学习笔记

一、概述

Kruskal 重构树(Kruskal Reconstruction Tree,KRT)是一种基于 Kruskal 最小/最大生成树算法构建的树形结构。它将原图中的边按权值排序后,通过并查集合并节点,每次合并时新建一个虚节点作为两个连通块的父节点,最终形成一棵二叉树(或多叉树)。

Kruskal 重构树的核心思想是:将边权信息转化为点权信息,从而利用树上的 LCA、倍增、子树查询等技巧高效解决原图的瓶颈路问题。


二、构建过程

2.1 算法步骤

  1. 初始化:原图有 $n$ 个节点,重构树初始有 $n$ 个叶节点(对应原图节点,权值设为 $-1$ 或无穷)。
  2. 排序:将边按权值排序。
    - 若求最大瓶颈路(即路径上最大边权的最小值),则边按降序排序。
    - 若求最小瓶颈路(即路径上最小边权的最大值),则边按升序排序。
  3. 合并:按顺序遍历每条边 $(u, v, w)$:
    - 找到 $u$ 和 $v$ 所在连通块的根 $ru, rv$。
    - 若 $ru = rv$,跳过。
    - 新建一个虚节点 $node$,权值设为 $w$。
    - 将 $ru$ 和 $rv$ 作为 $node$ 的两个子节点。
    - 在并查集中将 $ru, rv, node$ 合并,$node$ 为新的根。
  4. 倍增预处理:构建完成后,进行 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 或子树问题。其核心优势在于:

  1. 在线查询:构建一次,多次回答任意两点间的瓶颈路。
  2. 限制可达性:通过倍增跳祖先,快速定位满足边权约束的子树。
  3. 易于扩展:可与树剖、可持久化、差分等树上技术无缝结合。

掌握它,你将能轻松解决一类"边权限制下的连通性与最值"问题。


附录: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);
    }
};
← 返回博客列表
×