頂点 \(u\) とその子孫のうち \(k\) 個の頂点が黒く塗られる塗り方の個数を \(C(u, k)\) とし, \(u\) の子を \(v_i\) とする.

このとき, \(C(u, k)\) を DP で求める. \(u\) の \(i\) 番目の子まで見たときに \(j\) 子の頂点が黒く塗られる塗り方の個数を \(A(i, j)\) とすると,

\[A(i, j) = \sum_k A(i-1, j-k) C(v_i, k)\]

となる. これを更新していくと, \(C(u, k) = A(\abs{v}, k)\) となる. ただし, \(\abs{v}\) は \(u\) の子の数である.

そのまま計算すると \(O(N^3)\) となるが, \(C(u, k)\) の \(k\) は \(u\) とその子孫の数が上限であるので, そこまでで絞ることで \(O(N^2)\) に落とせる.