ABC036 D - 塗り絵

f:id:tkr987:20210313023300p:plain

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];

f:id:tkr987:20210313023856p:plain
葉から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]を出力すれば良い。