NeFut Logo NeFut
中 Admin Login

Kruskal Reconstruction Tree: An Elegant Transformation from Minimum Spanning Tree to Bottleneck Path Problem

Published at: 2026-05-29 01:49 Last updated: 2026-06-06 13:04
#algorithm #Data Structure #Graph

Core Logic and Mathematical Principles

This chapter focuses on the derived tactical form of Minimum Spanning Tree (MST) theory: Kruskal Reconstruction Tree (Kruskal Tree). This is an advanced data structure that transforms the edge weight information of a graph into node attributes of a tree.

1. Dimensional Mapping from Algebraic Space to Topological Space

The traditional Kruskal algorithm, when merging two connected components, merely points one root node to another in the disjoint set. The core physical essence of the Kruskal Reconstruction Tree is: a virtual node is created during each merge, which serves as a common parent of the root nodes of the two connected components.

This tree-building paradigm brings about an exquisite algebraic isomorphism property:

2. Spatial Transformation of the Bottleneck Path Problem

Solving the problem of "what is the minimum of the maximum edge weight among all paths from node $u$ to node $v$" in the original graph is essentially an MST bottleneck path problem. In the reconstruction tree, due to the max-heap property, the maximum edge weight on the path from leaf node $u$ to leaf node $v$ is elegantly transformed into the weight of the node at their Lowest Common Ancestor (LCA) in the reconstruction tree.

$$\text{Filter\textunderscore Edge\textunderscore Weight}(u, v) = \text{val}[\text{LCA}(u, v)]$$

This transformation flattens the complex graph path search directly into a static LCA query on the tree.

Algorithm Derivation and State Design

1. Dynamic Construction of the Reconstruction Tree

Define a counter node_idx = n to allocate numbers for newly generated virtual nodes. When Kruskal traverses an effective edge $(u, v)$ with weight $w$:

  1. Find the root nodes in the disjoint set: $root_u = \text{find}(u), \, root_v = \text{find}(v)$.
  2. If $root_u \neq root_v$, trigger a reconstruction upgrade:

$$\text{node\textunderscore idx} \leftarrow \text{node\textunderscore idx} + 1$$

$$\text{val}[\text{node\textunderscore idx}] = w$$

  1. Establish directed parent-child edges in the reconstruction tree: connect $ ext{node\textunderscore idx}$ to both $root_u$ and $root_v$.
  2. Update the base of the disjoint set: $\text{fa}[root_u] = \text{node\textunderscore idx}, \, \text{fa}[root_v] = \text{node\textunderscore idx}$.

2. Topologically Driven State Query (Reachability of Connected Components)

Classic Problem Description: Given a starting point $v$, which points can be reached by only passing through edges with weight $\ ext{\le} x$?

C++ Standard Source Code (Basic Framework Template for Kruskal Reconstruction Tree)

#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]; // The reconstruction tree nodes are doubled, and the disjoint set array must be allocated double space
long long val[MAXN * 2]; // Store the edge weight attributes of virtual nodes
std::vector<int> tr[MAXN * 2]; // Adjacency list of the reconstruction tree

// LCA doubling state
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 preprocess to build the doubling ancestors of the reconstruction tree
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);
    }
}

// Find the highest ancestor reachable by only passing through edges with weight <= max_w
int get_highest_ancestor(int v, long long max_w) {
    for (int k = 19; k >= 0; --k) {
        // If the ancestor exists and its associated original graph edge weight still satisfies <= max_w, jump upwards
        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;
    }

    // Core driver: sort edges in ascending order of weights
    std::sort(edges, edges + m);

    // Initialize the disjoint set base, space must be allocated for 2 * n
    for (int i = 1; i < 2 * n; ++i) dsu_fa[i] = i;

    int node_idx = n; // Virtual node numbering starts from 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; // New node takes on edge weight

            // Build edge in the reconstruction tree: point from new node to the old roots of both connected components
            tr[node_idx].push_back(root_u);
            tr[node_idx].push_back(root_v);

            // Merge into the new virtual node in the disjoint set
            dsu_fa[root_u] = node_idx;
            dsu_fa[root_v] = node_idx;

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

    // Note: If the graph itself is not connected, the reconstruction tree will be a forest.
    // To completely establish the doubling state, we must run DFS for each root of connected components (i.e., points where dsu_fa[i] == i)
    for (int i = node_idx; i >= 1; --i) {
        if (depth[i] == 0) { // Not visited, indicating it is the root of some tree
            int root = find_set(i);
            dfs_build(root, 0, 1);
        }
    }

    // Respond to reachability bottleneck queries
    while (q--) {
        int v;
        long long x;
        std::cin >> v >> x;

        int ans_node = get_highest_ancestor(v, x);
        // At this point, all leaf nodes in the subtree rooted at ans_node (numbered <= n) form the desired reachable point set
        std::cout << "Highest node ID: " << ans_node << ", Boundary weight: " << val[ans_node] << "\n";
    }

    return 0;
}

NOIP Practical Pitfall Guide

  1. Disjoint set and related reconstruction tree arrays not allocated double space: This is the classic point of failure in Kruskal's reconstruction tree. The original graph has only $N$ nodes, but the reconstruction tree will produce a total of $2N-1$ nodes. If contestants still allocate dsu_fa, val, depth arrays, or the doubling matrix parent with the traditional inertia of MAXN, when the program executes to node_idx > n, it will cause serious memory overflow, leading to runtime crashes (RE) or bizarre incorrect outputs. The iron rule must be: arrays involving the reconstruction tree node set must allocate double space.
  2. Multiple roots of the forest not handled leading to doubling topology gaps: If the original graph given in the problem is not fully connected, running Kruskal will create multiple independent trees (a reconstruction forest). If contestants blindly write a single line dfs_build(node_idx, 0, 1); in the main function, then the depth of other unconnected isolated blocks' virtual nodes and leaf nodes will remain 0, and the doubling ancestors cannot be established. Subsequent queries for points within these isolated blocks will lead to infinite loops or complete misinterpretation.

Classic NOIP/Luogu Problems

1. Luogu P1967 [NOIP2013 Advanced Group] Truck Transport

2. Luogu P4768 [NOI2018] Return Trip

  1. Base Layer: First, ignoring the rain restrictions, run Dijkstra's algorithm once on the original graph with point 1 as the source, to find the physical shortest walking distance $mindist[i]$ from each point to point 1.
  2. Space Reconstruction: Sort all edges by altitude from high to low (descending) and establish the Kruskal maximum reconstruction tree based on altitude attributes. The virtual nodes of the reconstruction tree record the altitude.
  3. Tree Query: When given a specific water level $p$ and starting point $v$, quickly jump upwards using doubling to find the shallowest virtual ancestor node $anc$ that satisfies val[anc] > p. At this point, all leaf nodes in the subtree rooted at $anc$ are the cities that can be reached by truck for free.
  4. Extreme Value Killing: To minimize the walking stamina consumption, we only need to find the minimum value of $mindist[i]$ among the leaf nodes that can be reached by truck. We can preprocess once on the tree using DFS to record min_d[u], the minimum $mindist$ of all leaf nodes in the subtree rooted at u. During queries, simply output min_d[anc], and the single query time complexity is only $O(\log N)$.
Original Source: local://11.4
[h] Back to Home
© 2026 Nefut. | About Us | Contact Us | Privacy Policy | RSS