bitDPによる解法を説明します。

プリム法のような感じで、ひとつの頂点が入った木を用意し、そこに辺と頂点を加えていきます。

DPの変数は \(\text{dp}[\text{木に含まれる頂点の集合}] = \{\text{コストの集合}\}\) となります。

DP の遷移では、木に含まれている頂点と木に含まれていない頂点を結ぶ辺を見つけ、これを木に加えます。

ここで注意するべきは、

• 元のコストが小さいほど良いとは限らないため、あり得るすべてのコストを保持する必要があるという点と、
• 辺を加えるときに辺のコストが小さいほど良いとは限らないため、あり得るすべての辺の追加を考える必要があるという点です。

計算量

• bitDP に \(O(2^N N^2)\) かかります。
  • 頂点集合を全探索するため \(O(2^N)\) かかります。
  • 木に含まれている頂点を選ぶのに \(O(N)\) かかります。
  • 木に含まれていない頂点を選ぶのに \(O(N)\) かかります。
• コストの種類数として、 \(O((M / N)^{N - 1})\) かかります。
  • 全域木の辺は最大でも \(N - 1\) 本であるため、頂点の次数を \(d\) としたとき \(O(d^{N - 1})\) かかり得ます。
  • 上の式が最悪となるのは \(d \in O(M / N)\) となるときです。

以上により、 \(O(2^N N^2 (M/N)^{N - 1})\) となるため、速い言語であれば時間制限内に間に合います。

コード

以下に C++ のコードを示します。 https://atcoder.jp/contests/abc328/submissions/47509050