Second Best Minimum Spanning Tree

A minimum spanning tree T of G connects all vertices with minimum total edge weight. A second-best MST T' is a spanning tree whose weight is the next-smallest among all spanning trees of G.

This lesson follows CP-Algorithms — Second best MST.

Related: Manhattan Distance (Manhattan MST), 0-1 BFS.

Observation

T' differs from T by exactly one edge replacement:

T' = (T ∪ {e_new}) \ {e_old}

with e_new ∉ T, e_old ∈ T, and T' still a tree. Among all such swaps, minimize

δ = weight(e_new) − weight(e_old)

(equivalently minimize the weight of T'). Proof sketch: see CLRS problem 23-1.

Slow approach: exclude each MST edge

1. Sort edges O(E log E), build MST with Kruskal O(E α(V)).
2. For each of the V−1 MST edges, forbid it and rebuild an MST on the rest (O(E) with edges already sorted).
3. Take the lightest alternative tree.

Complexity: O(V E).

Fast approach: add each non-MST edge + LCA

Do the dual:

1. Build MST T (weight res).
2. For every e = (u,v) ∉ T, adding e creates a unique cycle through LCA(u,v) in the rooted tree.
3. Let k be the heaviest edge on that cycle except e (i.e. max weight on tree paths u→LCA and v→LCA).
4. Candidate weight = res + w(e) − w(k). Keep the minimum.

With binary lifting that also stores path maxima (and optionally the second maximum when w(k) = w(e)), each query is O(log V). Total O(E log V).

Example (article intuition): add edge weight 36 → cycle 36–7–2–34 → drop 34 → δ = 2. Other non-tree edges give larger δ; the minimum δ tree is the second-best MST.

🧪 Kruskal MST + max-on-path swaps (toy graph)

Binary lifting sketch

Root the MST. For each node store:

up[v][j]  = 2ʲ-th ancestor
dp[v][j]  = (max, second_max) edge weights on the jump v → up[v][j]

combine merges two (max, second_max) pairs. Query lca(u,v) while folding dp along both ascent paths → heaviest (and second-heaviest) edge on the cycle when you add (u,v).

When the strict maximum equals w(e) (degenerate), fall back to the second maximum.

Reference: combine + LCA query idea

pair<int,int> combine(pair<int,int> a, pair<int,int> b) {
    // return top-two distinct values among {a.first,a.second,b.first,b.second}
}

pair<int,int> path_max(int u, int v); // lift + combine along u..v in the tree

// for each non-MST edge e=(s,e) with weight w:
auto rem = path_max(s, e);
int k = (rem.first != w) ? rem.first : rem.second;
ans = min(ans, res + w - k);

Full DSU + binary-lifting listing: CP-Algorithms.

Check: second-best MST

Quiz

Second-best MST

1 / 4

A second-best MST differs from the MST by…

Pick an answer to see if you are right.

Practice drills

Activity: Swap delta

Input: w_new w_old. Print w_new - w_old (the weight increase of that swap).

Practice problems

From CP-Algorithms:

• Codeforces — Minimum spanning tree for each edge

References: Competitive Programming 3 (Halim); MIT notes.

Cheat sheet

Idea	Takeaway
Structure	Second-best = MST with one edge swap
Slow	Forbid each MST edge, re-Kruskal → O(V E)
Fast	For each e ∉ T, drop max on cycle → O(E log V) with LCA
Tool	Binary lifting + path max (top-two)
Output	res + min (w(e) − w(k))