問題

$N$ 頂点 $M$ 辺の重みつき単純連結無向グラフが与えられる。辺 $i$ は頂点 $A_i$ と $B_i$ を結び、重みは $C_i$ である。辺 $1$ から $M$ それぞれについて、その辺を含む最小の重みの全域木を求める。

考察

与えられた連結グラフの最小の重みの全域木とその重みを求める。この全域木に含まれる辺はこれで求められる。

それ以外の辺 $i$ について考える。作った全域木に辺 $i$ を追加すると、全域木上の頂点 $A_i$ と $B_i$ を結ぶパスと辺 $i$ で閉路ができ、この閉路上の任意の辺を1つ除くと再び全域木ができることがわかる。取り除く辺は辺 $i$ 以外の閉路上の辺のうち、もっとも重みが大きいものでよい（証明を後述）。

閉路上のもっとも重みの大きい辺を見つけるにはLowest Common Ancestorのアルゴリズムが使える。計算量は $\mathcal{O}(N \log N)$ になる。

証明

[補題] 辺 $i$ を含むグラフ上の最小全域木は、最小全域木 $\mathcal{T}$ に辺 $i$ を追加し、 $\mathcal{T}$ での頂点 $A_i$ と $B_i$ のパス上の辺のうちもっとも重みの大きい辺を除いたグラフと一致する

クラスカル法では、連結グラフの重みの小さい辺から順番に、現在作っている全域木に追加しても閉路を作らないもののみを追加することで最小全域木 $\mathcal{T}$ を構築する。

頂点 $A_i$ と $B_i$ を結ぶ、 $\mathcal{T}$ に含まれない辺 $i$ について考える。 $\mathcal{T}$ で頂点 $a$ と $b$ のパス上の辺は $e_{p(1)}, e_{p(2)}, \cdots, e_{p(k)}$ で、 $C_{p(1)} \leq C_{p(2)} \leq \cdots \leq C_{p(k)}$ を満たす。

頂点 $A_i$ と $B_i$ を辺 $i$ で結んだ状態からクラスカル法を用いて、この条件下での最小全域木 $\mathcal{T}^\prime$ を求める。辺 $e_{p(1)}, e_{p(2)}, \cdots, e_{p(k)}$ は、番号 $p(1), p(2), \cdots, p(k)$ の順に追加されるが、 $e_{p(k)}$ を追加すると閉路ができるため、 $e_{p(k)}$ は追加されない。また、頂点 $A_i$ と $B_i$ のパス上以外の辺は、これに影響されないので、 $\mathcal{T}$ と同じ辺を使うことができる。