ix. Kruskal Reconstruction Tree

Run Kruskal, but whenever an edge of weight $w$ joins two components, create a new node with weight $w$ whose children are the two components’ current tree nodes. The result is a binary tree whose leaves are the original vertices and whose node weights never decrease going up. It answers bottleneck questions directly:

• the minimum over all $u$–$v$ paths of the maximum edge weight is the weight of $\text{LCA}(u,v)$;
• the vertices reachable from $v$ using only edges of weight $\le x$ are the leaves under the highest ancestor of $v$ with weight $\le x$, a contiguous range of the leaf order.

template <class T> struct KruskalTree {                  // feed edges in non-decreasing weight
    int n; DSU dsu; vector<int> par, top, dep, order, lo, hi; vector<array<int, 2>> ch; vector<T> w; vector<vector<int>> up;
    KruskalTree(int n) : n(n), dsu(n), par(n, -1), top(n), ch(n, {-1, -1}), w(n, T()) { iota(all(top), 0); }
    int addEdge(int u, int v, T wt) {                     // the new node id, or -1 if already connected
        int a = dsu.find(u), b = dsu.find(v); if (a == b) return -1;
        int x = sz(par); par[top[a]] = par[top[b]] = x; par.push_back(-1); ch.push_back({top[a], top[b]}); w.push_back(wt);
        dsu.unite(a, b); top[dsu.find(a)] = x; return x;
    }
    void build() {                                       // after the last edge
        int m = sz(par), lg = 1; while ((1 << lg) < m) lg++;
        up.assign(lg, vector<int>(m)); dep.assign(m, 0);
        for (int x = m - 1; x >= 0; x--) { up[0][x] = par[x] < 0 ? x : par[x]; if (par[x] >= 0) dep[x] = dep[par[x]] + 1; }   // par[x] > x
        for (int k = 1; k < lg; k++) for (int x = 0; x < m; x++) up[k][x] = up[k - 1][up[k - 1][x]];
        vector<int> cnt(m, 1); for (int x = n; x < m; x++) cnt[x] = cnt[ch[x][0]] + cnt[ch[x][1]];
        lo.assign(m, 0); hi.assign(m, 0); order.assign(n, 0); int next = 0;
        for (int x = m - 1; x >= 0; x--) {                // leaves under x are order[lo[x] .. hi[x])
            if (par[x] < 0) lo[x] = next, next += cnt[x];
            hi[x] = lo[x] + cnt[x];
            if (x < n) order[lo[x]] = x; else lo[ch[x][0]] = lo[x], lo[ch[x][1]] = lo[x] + cnt[ch[x][0]];
        }
    }
    int lca(int u, int v) const {                         // -1 if disconnected
        if (dep[u] < dep[v]) swap(u, v);
        for (int k = sz(up) - 1; k >= 0; k--) if (dep[u] - (1 << k) >= dep[v]) u = up[k][u];
        if (u == v) return u;
        for (int k = sz(up) - 1; k >= 0; k--) if (up[k][u] != up[k][v]) u = up[k][u], v = up[k][v];
        return up[0][u] == up[0][v] ? up[0][u] : -1;
    }
    int ancestor(int v, T x) const {                      // highest ancestor with weight <= x (v itself if none)
        for (int k = sz(up) - 1; k >= 0; k--) { int a = up[k][v]; if (a >= n && w[a] <= x) v = a; }
        return v;
    }
};

For maximum bottleneck (widest path), feed edges in non-increasing order and read w[a] >= x. With vertex weights (“pass only through vertices with value $\le x$”), add vertices in increasing value and join each to its already-added neighbours, giving the node the vertex’s value.

Problem	Use
minimax path weight between $u,v$ (many queries)	w[lca(u, v)]
from $v$, using edges $\le x$: how many / which vertices, $k$-th largest value among them	ancestor(v, x), then a range of order (prefix sums, wavelet / persistent tree)
two constraints (IOI “Werewolf”: go through high vertices, then low vertices)	two trees, a 2D rectangle query on (position in tree 1, position in tree 2)
offline “time when $u$ and $v$ become connected”	w[lca(u, v)] with edge index as weight
minimum spanning tree path maximum	same as minimax: it lies on the MST

Proof: bottleneck = LCA weight, reachable sets = subtrees

Monotone weights: a node is created after its children, from an edge processed later, so its weight is $\ge$ theirs; hence ancestor is a monotone search and $\text{par}[x]>x$. Subtrees are components: by induction, after processing all edges of weight $\le x$, the DSU components are exactly the leaf sets of the current top nodes, and every node created so far has weight $\le x$. So the component of $v$ in the graph restricted to edges $\le x$ is the leaf set of the highest ancestor of $v$ with weight $\le x$. Minimax: $u$ and $v$ are connected using edges $\le x$ iff they share that component iff $\text{LCA}(u,v)$ has weight $\le x$ (the LCA is created exactly when their components merge). So the smallest such $x$, the minimax path value, is the LCA’s weight. Leaf ranges: the build lays out each node’s leaves contiguously (left child’s block then right child’s block, roots in turn), so a subtree is the interval $[\text{lo},\text{hi})$.