この記事は、EDPC の P ~ S 問題の解説です。P ~ S 問題を解いてみてから読まれることを推奨します。

O 問題までを解いていない方は、これらの記事も読まれるといいと思います。

$N$ 頂点の木の各頂点を白黒に塗り分ける方法が何通りあるか、$\mod{10^9+7}$ で求めてください。 ただし、黒で塗った頂点は隣り合ってはいけません。

適当な頂点を根として、根付き木として考えます。 根付き木の各頂点について、その頂点の子についての情報から DP テーブルの値を更新していく DP は木 DP と呼ばれています。

頂点 $u$ を頂点とする部分木について、この問題と同じ問題を解くことを考えます。 $u$ に塗る色で場合分けをして考えてみます。

このことから、$u$ を白で塗った時の題意を満たす通り数 $w_u$ と、黒で塗った時の通り数 $b_u$ を DP としてテーブルに保存しておけば解けます。

「メモ化再帰」と言っても木上の DFS で各頂点にアクセスするのは $1$ 回だけなので、実質ただの再帰みたいなところはあります。(DP テーブル無しでも実装することができます。ぜひ挑戦してみましょう。)

計算量は $O(N)$ です。