https://atcoder.jp/contests/abc036/submissions/20748614
- 初期値はall(dp) = 1;
- 繰り返しは DFS
- 漸化式は dp[now][B] *= dp[next][W], dp[now][W] *= dp[next][B] + dp[next][W];
- 最終目標は dp[0][B] + dp[0][W];
葉からDPを更新することで根が答えになる。頂点を黒く塗るのはnextが白のときだけなのでdp[now][B] *= dp[next][W]、頂点を白く塗るのはnextの色は何でも良いのでdp[now][W] *= dp[next][B] + dp[next][W]でnextの白黒両方の場合の数を乗算していく。根を頂点0にしたときはdp[0][B] + dp[0][W]を出力すれば良い。
DFSはnowでの処理は①、nextに遷移しながら処理するなら②、nextからnowへ戻りながら処理するなら③、に書くと暗記すると良いかと思う。