No.196

頂点 $v$ を根とする木で $k$ 個の頂点を黒く塗る組み合わせの数を $A(v, k)$ とする.

頂点 $v$ が持つ子の個数を $n_v$, 子をそれぞれ $c_0, c_1, \dots, c_{n_v-1}$ とし, 頂点 $v$ の最初の $i$ 個の子のみがあるとして, $k$ 個の頂点を黒く塗る組み合わせの数を $B_v(k, i)$ とする.

このとき,

$$B_v(k, i) = \sum_j B_v(k-j, i-1) \cdot A(c_i, j)$$

で計算できる. あとは $A(v, k) = B_v(k, n_v)$ を葉から順に計算する. 葉から順にたどるには, 深さ優先探索や幅優先探索で頂点を列挙し, 列挙された頂点を逆からたどればいい.

ただ, そのまま計算すると計算量が $O(N^3)$ となるので, $v$ の子孫の数をあらかじめ数えておき, $k$ がそれ以上なら計算しないようにして枝刈りをする.