Second-Best MST

The second-best MST is a spanning tree of minimum weight among those different from the MST. It always differs from the MST by exactly one edge swap.

Why one swap suffices

Claim. There is a second-best MST $T^{\prime }$ with $|T△T^{\prime }|=2$ — one edge removed, one added.

Proof sketch. Let $T$ be an MST and $T^{\prime }$ a second-best tree differing in $\ge 2$ edges. Take $e\in T^{\prime }\setminus T$; adding $e$ to $T$ makes a cycle containing some $f\in T\setminus T^{\prime }$. Then $T+e-f$ is a spanning tree with weight $\ge w(T)$ (since $T$ is minimum) and $\le w(T^{\prime })$, and it differs from $T$ in exactly one swap. So a single-swap tree is at least as good as $T^{\prime }$. ∎

Algorithm — $O(E\log E+E\log V)$

1. Build the MST.
2. Preprocess the MST so that the maximum edge weight on the tree path between any two vertices can be queried in $O(\log V)$ — binary lifting with a max aggregate is the easiest way.
3. For each non-tree edge $(u,v,w)$, compute $M=\mathrm{pathMax}(u,v)$. Adding the edge and removing that maximum gives weight $w(T)+w-M$.
4. Take the minimum over all non-tree edges with $w>M$ — strictly greater, otherwise you would produce the same-weight tree, which may be the MST itself.

long long secondBestMST(int n, vector<Edge>& edges) {
    long long mstWeight = buildMST(n, edges);        // marks inMST[i]
    buildBinaryLiftingWithMax(n);                    // mx[v][k]
 
    long long best = LLONG_MAX;
    for (auto& [w, u, v, id] : edges) {
        if (inMST[id]) continue;
        long long m = pathMax(u, v);
        if (w > m) best = min(best, mstWeight + w - m);
    }
    return best;                                     // LLONG_MAX if none exists
}

Equal weights

If duplicate weights exist, w > m may exclude every candidate even though a different tree of the same weight exists. Decide which the problem wants:

• strictly greater weight → keep w > m;
• any different tree → also track the largest edge on the path that is strictly less than $w$ (the “second maximum”), which allows an equal-weight swap producing a genuinely different tree.

Track both the maximum and the second maximum in the binary-lifting aggregate to handle both cases.

Tracking two maxima

struct Two { long long mx1, mx2; };               // strictly mx2 < mx1
 
Two merge(Two a, Two b) {
    Two r;
    r.mx1 = max(a.mx1, b.mx1);
    r.mx2 = max(a.mx1 == r.mx1 ? a.mx2 : a.mx1,
                b.mx1 == r.mx1 ? b.mx2 : b.mx1);
    return r;
}

Then for a candidate edge of weight $w$: swap out mx1 if $w>mx1$, else swap out mx2 if $w>mx2$.

Related problems

Problem	Approach
$k$-th best spanning tree	Gabow’s algorithm, or repeated partitioning on forced-in/forced-out edges
MST after increasing one edge’s weight	if it is a tree edge, look for a replacement on its cut; otherwise unchanged
MST after decreasing one edge’s weight	add it and remove the max edge on the cycle formed
Is the MST unique?	unique iff no non-tree edge has $w=\mathrm{pathMax}$
For each edge: is it in every / some MST?	in every MST iff it is the strict minimum on some cut; in some MST iff it is not the strict maximum on any cycle — computable per weight class with DSU + bridge finding

The “every / some MST” classification is a nice piece of theory worth knowing: group edges by weight, contract everything cheaper, and within each weight class an edge is in some MST iff it connects two different contracted components, and in every MST iff it is a bridge of the graph formed by that weight class.

See also: Minimum Spanning Tree · Binary Lifting · Kruskal