Kruskal重构树：最小生成树的高级数据结构与应用

核心逻辑与数学原理

本章聚焦于最小生成树（MST）理论的衍生战术形态：Kruskal重构树（Kruskal Reconstruction Tree / Kruskal Tree）。这是一种将图的边权信息转化为树的节点属性的高级数据结构。

1. 代数空间向拓扑空间的升维映射

传统的Kruskal算法在合并两个连通块时，仅仅是在并查集中将一个根节点指向另一个根节点。而Kruskal重构树的核心物理本质是：在每次合并时，新建一个虚拟节点，以此虚拟节点作为两侧连通块根节点的共同父亲。

这种建树范式带来了极为精妙的代数同构特性：

• 节点数重构：原图有 $N$ 个点，经过 $N-1$ 次合并后，重构树将包含 $N$ 个叶子节点（对应原图的节点）和 $N-1$ 个非叶子内部节点（对应合并时的边），总计 $2N-1$ 个节点。
• 边权属性节点化：原图的边权被赋予给每次新建的虚拟节点。若Kruskal按边权升序（求MST）排序，则重构树将天然满足大根堆性质（即任何一个虚拟节点的权值都大于或等于其子树中所有虚拟节点的权值）。

2. 瓶颈路问题的空间化转化

在原图上求解“从点 $u$ 到点 $v$ 的所有路径中，最大边权的最小值是多少”，本质是一个MST瓶颈路问题。在重构树上，由于大根堆性质，从叶子节点 $u$ 走到叶子节点 $v$ 路径上的最大边权，被优雅地转化为它们在重构树上的最近公共祖先（LCA）的节点权值。

$$\text{Filter\_Edge\_Weight}(u, v) = \text{val}[\text{LCA}(u, v)]$$

这一转化将复杂的图论路径搜索，直接降维拉平为树上的静态LCA查询。

算法推导与状态设计

1. 重构树的动态构建

定义计数器 node_idx = n，用于为新产生的虚拟节点分配编号。在Kruskal遍历到一条有效边 $(u, v)$，权值为 $w$ 时：

1. 寻找并查集根节点：$root_u = \text{find}(u), \, root_v = \text{find}(v)$。
2. 若 $root_u \neq root_v$，触发重构升级：

$$\text{node\_idx} \leftarrow \text{node\_idx} + 1$$

$$\text{val}[\text{node\_idx}] = w$$

3. 在重构树中建立有向父子边：从 $\text{node\_idx}$ 分别连向 $root_u$ 和 $root_v$。
4. 更新并查集基座：$\text{fa}[root_u] = \text{node\_idx}, \, \text{fa}[root_v] = \text{node\_idx}$。

2. 状态查询拓扑驱动（连通块可达性）

经典问题描述：求从点 $v$ 出发，只经过边权 $\le x$ 的边，能到达哪些点？

• 状态推导：在按升序建立的重构树中，由于大根堆性质，我们可以从叶子节点 $v$ 开始向上倍增跳跃（利用 fa[v][k] 矩阵），一直跳到一个深度最浅且满足 $\text{val}[anc] \le x$ 的祖先节点 $anc$。
• 区间转化：此时，以 $anc$ 为根的子树中所有的叶子节点，就是从 $v$ 出发满足约束的可达点集。通过对重构树跑一次DFS建立DFS序（欧拉序），可将“子树内所有叶子节点”映射为一段连续的数组区间 $[L[anc], R[anc]]$。配合主席树（可持久化线段树）或树状数组，即可在 $O(\log N)$ 内演变为各种复杂的区间检索问题。

C++ 标准源码（Kruskal重构树基础架构模板）

#include <iostream>
#include <vector>
#include <algorithm>

const int MAXN = 100005;
const int MAXM = 300005;

struct Edge {
    int u, v;
    long long w;
    bool operator<(const Edge& rhs) const { return w < rhs.w; }
};

Edge edges[MAXM];
int dsu_fa[MAXN * 2]; // 重构树节点翻倍，并查集数组必须开两倍空间
long long val[MAXN * 2]; // 存储虚拟节点的边权属性
std::vector<int> tr[MAXN * 2]; // 重构树的邻接表

// LCA 倍增状态
int depth[MAXN * 2];
int parent[MAXN * 2][20];

int find_set(int i) {
    if (dsu_fa[i] == i) return i;
    return dsu_fa[i] = find_set(dsu_fa[i]);
}

// DFS 预处理重构树的倍增祖先
void dfs_build(int u, int p, int d) {
    depth[u] = d;
    parent[u][0] = p;
    for (int k = 1; k < 20; ++k) {
        parent[u][k] = parent[parent[u][k-1]][k-1];
    }
    for (size_t i = 0; i < tr[u].size(); ++i) {
        int v = tr[u][i];
        dfs_build(v, u, d + 1);
    }
}

// 寻找满足只通过权值 <= max_w 的边能跳到的最高祖先
int get_highest_ancestor(int v, long long max_w) {
    for (int k = 19; k >= 0; --k) {
        // 如果祖先存在，且其关联的原图边权仍满足 <= max_w，则向上跳跃
        if (parent[v][k] != 0 && val[parent[v][k]] <= max_w) {
            v = parent[v][k];
        }
    }
    return v;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m, q;
    if (!(std::cin >> n >> m >> q)) return 0;

    for (int i = 0; i < m; ++i) {
        std::cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    // 核心驱动：按边权升序排列
    std::sort(edges, edges + m);

    // 并查集底座初始化，空间必须开齐 2 * n
    for (int i = 1; i < 2 * n; ++i) dsu_fa[i] = i;

    int node_idx = n; // 虚拟节点编号从 n + 1 开始
    int edge_cnt = 0;

    for (int i = 0; i < m; ++i) {
        int root_u = find_set(edges[i].u);
        int root_v = find_set(edges[i].v);

        if (root_u != root_v) {
            node_idx++;
            val[node_idx] = edges[i].w; // 新节点托管边权

            // 重构树建边：从新节点指向两侧连通块的旧根
            tr[node_idx].push_back(root_u);
            tr[node_idx].push_back(root_v);

            // 并查集归拢到新虚拟节点上
            dsu_fa[root_u] = node_idx;
            dsu_fa[root_v] = node_idx;

            edge_cnt++;
            if (edge_cnt == n - 1) break;
        }
    }

    // 注意：若图本身不连通，重构树会是一个森林。
    // 为了完备建立倍增状态，必须对每个联通块的根（即 dsu_fa[i] == i 的点）都跑一遍 DFS
    for (int i = node_idx; i >= 1; --i) {
        if (depth[i] == 0) { // 未被访问过，说明是某棵树的根
            int root = find_set(i);
            dfs_build(root, 0, 1);
        }
    }

    // 响应可达性瓶颈询问
    while (q--) {
        int v;
        long long x;
        std::cin >> v >> x;

        int ans_node = get_highest_ancestor(v, x);
        // 此时，以 ans_node 为根的子树内所有的叶子节点（编号 <= n 的点）即为所求可达点集
        std::cout << "Highest node ID: " << ans_node << ", Boundary weight: " << val[ans_node] << "\n";
    }

    return 0;
}

NOIP 实战避坑指南

1. 并查集及相关重构树数组空间未开双倍： 这是Kruskal重构树最经典的爆零点。原图只有 $N$ 个点，但重构树总共会产生 $2N-1$ 个节点。如果选手的 dsu_fa、val、depth 数组或者倍增矩阵 parent 仍然按照传统惯性开辟成 MAXN，在程序执行到 node_idx > n 时会发生严重的内存越界覆盖，导致运行时崩溃（RE）或输出诡异错解。必须铁律：涉及重构树点集的数组开双倍空间。
2. 森林多根未处理导致倍增拓扑断层： 如果题目给出的原图不是完全连通的，Kruskal跑完后会形成多棵独立的树（重构森林）。如果选手在 main 函数中盲目地只写一句 dfs_build(node_idx, 0, 1);，那么其余未连通孤立块的虚拟节点和叶子节点的深度 depth 将全部保持为0，倍增祖先也无法熟化。后续如果查询这些孤立块内的点，会导致死循环或彻底错解。

经典 NOIP/洛谷 真题

1. 洛谷 P1967 [NOIP2013 提高组] 货车运输

• 题意描述： 给定一个由 $N$ 个点、$M$ 条无向边组成的图，边上有载重限制。有 $Q$ 个询问，每次给出起点 $x$ 和终点 $y$，求货车从 $x$ 到 $y$ 所有路径中，能够运送的货物的最大重量（即路径上最小边权的最大值）。
• 问题本质与核心思路： Kruskal重构树的最标准开山真题。 要求“最小值的最大值”，属于最大生成树瓶颈路问题。核心战术：将边权从大到小（降序）排序，构建 Kruskal最大重构树。由于是最大重构树，其虚拟节点天然满足小根堆性质（越往上权值越小）。建树完毕后，针对每次询问 $(x, y)$，如果两点在并查集中最终不连通，直接输出-1。若连通，则货车能运送的最大重量，严格等于它们在重构树上的最近公共祖先（LCA）的节点权值 val[LCA(x, y)]。利用倍增LCA可在 $O(\log N)$ 时间内完美秒杀。

2. 洛谷 P4768 [NOI2018] 归程

• 题意描述： 一张图上有 $N$ 个点、$M$ 条边。每条边有两个属性：长度 $l$ 和海拔高度 $a$。每天下雨会有一个积水水位 $p$。如果一条边的海拔 $a > p$，货车可以通过它顺利通行（且不消耗体力）；若 $a \le p$ 则该边积水，货车无法通行，必须下车步行。步行通过一条边消耗的体力等于边长 $l$。货车司机想知道，从起点 $v$ 出发回到终点 $1$ 号点，最少需要消耗多少体力？
• 问题本质与核心思路： 这是Kruskal重构树 + 单源最短路的殿堂级综合应用。 核心拆解战术：车辆可以免费通行的充要条件是只走海拔 $a > p$ 的边。这本质上就是求：从起点 $v$ 出发，只经过海拔 $> p$ 的边，能够开车到达的连通块可达点集。

1. 底层底座：首先无视下雨限制，在原图上以 $1$ 号点为源点，利用Dijkstra算法跑一次全量单源最短路，求出每个点到 $1$ 号点的物理最短步行距离 $mindist[i]$。
2. 空间重构：将所有边按照海拔高度从大到小（降序）排列，建立海拔属性的 Kruskal最大重构树。重构树的虚拟节点记录海拔。
3. 树上检索：当给出一个特定的水位 $p$ 和起点 $v$ 时，利用倍增快速向上跳跃，找到深度最浅且海拔 val[anc] > p 的虚拟祖先节点 $anc$。此时，以 $anc$ 为根的子树内所有的叶子节点，就是开车能免费到达的所有城市。
4. 极值秒杀：为了让步行消耗的体力最少，我们只需要在这群开车可达的叶子节点中，找出 $mindist[i]$ 最小的那个值即可。我们可以通过一次树上DFS预处理，用 min_d[u] 记录以 u 为根的子树中所有叶子节点的 $mindist$ 最小值。查询时直接输出 min_d[anc] 即可，单次查询时间复杂度仅为 $O(\log N)$。