yukicoder No.196 典型DP (1)

• 問題

問題概要

N頂点の0を根とする木が与えられる. 木を白黒に塗る.
ある頂点が黒の時,その子が全て黒であるという制約を満たしながら塗る時,黒の数がKであるのは何通りか.

解法

dp[i][j] := (i頂点以下で黒がj個の場合の数)とする.
初期値は dp[i][0] = 1, dp[i][j] = 0 (j!=0)
遷移はiの子をi'として,dp[i][j] = sum_(k+l=j)(dp[i][k]*dp[i'][l])
毎回遷移で0<=k,l<=K としてしまうと計算量T(x)は
T(x+1) = T(x) + K² より O(N³) となる.
しかしi'を取り込む前のiを除いたiの部分木のサイズx, i'の部分木のサイズをyとすると,
0<=k<=x,0<=l<=rだけ見ればよく, T(x+y) = T(x) + T(y) + xy でこれは T(x) = O(xy) = O(N²)となる.
よってDFSと同時に部分木のサイズを求めていき,その範囲だけkとlを動かせば良い.
dp[i][x] = 1となる点にも注意(iを黒に塗る場合はi以下も全て黒になり,これは1通り)

メモ

計算量落ちるのを知らなかったので解けなかった.
畳み込みっぽいしもしかして毎回FFTしても解けるかも?

コード