まずは、\(k\) を固定した場合に問題を解きましょう。 各辺の重みを、頂点番号が \(k\) 以下の端点の個数 (\(=0,1,2\))に設定して、最大全域木を求めればよいです。 これを各 \(k\) について回すととても間に合わないので、最大全域木の様子を考えます。

最大全域木の重みを求めるアルゴリズムとして、クラスカル法を考えます。 ここで、重み \(2\) の辺が使われる回数を考えます。 これは、\(N-(\)重み \(2\) の辺だけ考えたときにできる連結成分の個数\()\) と書けます。

当たり前ですが、\((\)重み \(2\) の辺だけ考えたときにできる連結成分の個数\()\) は、辺の順番に依存しません。 よって、\(k\) を \(1\) つずつ増やしながら、重み \(2\) の辺を増やし、そのたびに連結成分の個数を確認すればよいです。 これは union-find を使うことで高速に計算できます。

重み \(1\) の辺についても同様に処理します。 最大全域木において、重み \(1\) 以上 の辺が使われる回数に注目すると、重み \(2\) の辺とまったく同様の議論が行えます。 そして、同様の手順で計算が行えます。

これらをまとめると、結局 \(2\) つの union-find を持って \(k\) の小さいほうから計算していくことになります。 計算量は \(O(M \alpha (N))\) になります。(ここで \(\alpha(x)\) はアッカーマン関数の逆関数です)

実装例