与えられたグラフを \(G\) とします。

\(G\) の部分グラフ \(G'\)に対して多項式 \(dp[G']\) を、\(k\) 次の係数が「\(k-1\) 回の操作では不可能で、\(k\) 回の操作では可能な塗り分け方の数」であるものと定めます。 ただし、\(k=0\) のときは、すべての頂点が黒のままである塗り分けに対応する \(1\) と定義します。 (多項式で定義するのは、以下の説明を簡単にするためであり、本質的ではありません)

\(1\) 頂点しか塗られない場合以外の全ての操作は「辺 \(e\)を選び、重みが \(e\) の重み以下の辺のみを通って \(e\) からたどり着ける頂点を全て赤く塗る」と読み替えることができます。

グラフが木で、辺の重みが相異なる場合

辺のないグラフから始めて、重みの小さい順に辺を追加することを考えます。追加する辺 \(e\) が、連結成分 \(C_1\) と \(C_2\) を連結して連結成分 \(C\) になるとき、

• \(e\) に対して操作を行わないならば、\(C_1\) と \(C_2\) に対する操作は独立になる
• \(e\) に対して操作を行うならば、\(C\) の頂点は全て赤く塗られる

となるため、\(dp[C]=dp[C_1]*dp[C_2]-X^2+X\) となります。この計算は、高々 \(K\) 次の多項式同士の積なので \(O(K^2)\) で求められます。dpテーブルの計算は辺を追加するごとに行われるので、\(dp[G]\) を求めるには全体で \(O(NK^2)\) でかかるように見えますが、実は \(O(NK)\) になっていることが示せます(後述)。

重みが等しい辺が存在する場合

重みが同じ辺は同時に追加するとします。このとき、連結成分 \(C_1,\ldots,C_m\) が連結されて連結成分 \(C\) になるとき、先程と同様に、新しく追加された辺を使うかどうか場合分けして考えることで、\(dp[C]=\prod dp[C_i] - X^m+X\) となることが示せます。辺を \(m-1\) 本追加して乗算を \(m-1\) 回行うので、計算量は前のケースと同じになります。

グラフが木でないとき

最小全域木 \(T\) を \(1\) つ固定して考えれば良いです。なぜなら、\(T\) に含まれない辺 \(e\) について以下が成り立つためです。

• \(T\) に含まれる辺に対する操作は、\(e\) の有無に影響を受けない
• \(e\) に対する操作は、\(T\) に含まれる重み最大の辺に対する操作と同じ（\(G\) の全ての頂点が赤く塗られる）

計算量解析

\(2\) つの連結成分を連結するとき、それらの頂点数が \(K\) 以上かどうかで場合分けをします。

• \(2\) つとも \(K\) 以上のとき
  そのような連結は \(O(N/K)\) 回しか起こらず、各 \(O(K^2)\) 時間で計算できるため、全体で \(O(NK)\) になります。
• \(2\) つとも \(K\) 未満のとき
  連結後に初めて \(K\) より大きくなるときに、それまでの連結の過程の計算量を全て考えるとします。連結過程の計算量は \(O(K^2)\) 時間であり、\(O(N/K)\) 個の連結成分が残るので、全体で \(O(NK)\) になります。
• 一方が \(K\) 以上で他方が \(K\) 未満のとき
  各要素について、\(K\) 未満の連結成分側としてはこのような連結は高々 \(1\) 回しか行われないため、全体で \(O(NK)\) になります。

以上より全体で \(O(NK)\) となることが確かめられました。

参考文献： 木と計算量 前編 〜O(N^2)とO(NK)の木DP〜 (snukeさんのブログ)