No.036 D

島は木構造になっているので, 島 $1$ を根とする根付き木を作成する. 島 $i$ の子の集合を $C_i$ とし, 島 $i$ を白/黒に塗るときの島 $i$ を含む子孫の塗り方の数をそれぞれ $W_i$, $B_i$ とする.

このとき, $B_i$ は簡単に求められて,

$$B_i = \prod_{j \in C_i} W_j$$

となり, $W_i$ は, その子供の白黒のパターンをすべて足したものなので,

$$W_i = \prod_{j \in C_i} (W_j + B_j)$$

となる. (上記の式を展開してみればわかる)

あとはこれを葉から順に計算していって, $B_1 + W_1$ が答えとなる.