辺 \(i\) の重みを \(w_i\) とします。 \(G\) の全域木 \(T\) に対して、次が成り立つことが知られています。

「\(T\) は \(G\) の最小全域木である」⇔「\(T\) に含まれない \(G\) の任意の辺 \(x\) をとると、\(T\) 上の \(u_x\) と \(v_x\) を結ぶパスに含まれる任意の辺 \(y\) について \(w_y \le w_x\) \((*)\) 」

解法

赤い辺で構成された \(G\) の全域木を \(T\) とします。

\(w_i\) に \(1\) から \(M\) までの整数を \(1\) つずつあてはめて、条件を満たす \(w(=p)\) の中で辞書順最小のものを作ることにします。

すべての \(w_i\) の値が決まるまで、以下の手続きを繰り返します。

手続き

\(id\) をまだ \(w_i\) の値を決めていない \(i\) の最小値、\(m\) をまだ使っていない整数の最小値とします。ここで、\(m\) 以上の整数はまだ使われていないことが、手続きの定義より帰納的に示せます。

\(c_{id} = 1\) のとき（辺 \(id\) が赤い辺のとき）

\(w_{id} = m\) としてもまだ条件を満たす \(w\) は存在します。例えば、まだ使っていない整数の中で小さいものをすべて赤い辺に、残ったものをすべて青い辺に割り当てればよいです。

\(j < id\) について \(w_j\) の値は決まっているので、辞書順最小となる \(w\) は \(w_{id} = m\) を満たします。

\(c_{id} = 0\) のとき（辺 \(id\) が青い辺のとき）

\(T\) 上の \(u_{id}\) と \(v_{id}\) を結ぶパスに含まれる辺 \(y\) のなかで、\(w_y\) がまだ決まっていない \(y\) を昇順にならべて \(y_1, y_2, \ldots, y_k\) とします。

\(w_{y_i} = m + i -1 (1 \le i \le k)\) および \(w_{id} = m + k\) としてもまだ条件を満たす \(w\) は存在します。例えば、まだ使っていない整数の中で小さいものをすべて赤い辺に、残ったものをすべて青い辺に割り当てればよいです。

もし \(w_{id} < m + k\) とすると、\(w_{id} < w_{y_i}\) となる \(y_i\) が存在してしまうため、上の \((*)\) を満たさず \(T\) は全域木ではなくなってしまいます。

\(j < id\) について \(w_j\) の値は決まっているので、辞書順最小となる \(w\) は\(w_{y_i} = m + i -1 (1 \le i \le k)\) および \(w_{id} = m + k\) を満たします。

実装

上の解法を愚直に実装すると \(O(MN)\) かかってしまいますが、Union Find などのデータ構造や “データ構造をマージする一般的なテク” というテクニックを用いると \(O(M \alpha(N) )\) や \(O(M \log N)\) などで解くことができます。