https://atcoder.jp/contests/dp/submissions/12329034
- 初期値はall(dp)=1
- 繰り返しはDFSの再帰
- 漸化式はdp[i][stW] *= (dp[i][stB]+dp[i][stW]); / dp[i][stB] *= dp[i][stW];
- 最終目標はdp[0][stW] + dp[0][stB]
親が白なら子は白と黒の両方あり得る。親が黒なら白一択。v2の5通り各々に対して更にv3の2通りがあるので、例えばv1が白だったときの組み合わせは5x2=10になる。「dp *= にゃあ」のように乗算で増えていくのでdpの初期値を0でなく1にしておくと実装が楽になる。また、DFSにおける親の頂点処理はfor文の前に書き、上から下への処理は再帰関数の前に書き、下から上への処理は再帰関数の後に書くと暗記すると良いかと思う。
