DPまとめコンテスト/P - Independent Set - 競技プログラミング用 知識集積所【7/19更新】

---

問題

DP-P

必要知識

ABCのB以下レベルの内容は省略

• 動的計画法
• 根付き木（未作成）
• トポロジカルソート（未作成）
• 剰余類環

考え方

G問題の類似品。

木（未作成）を根付き木（未作成）のような有効非巡回グラフに加工。
トポロジカルソート（未作成）。
後ろから順に動的計画法。
以上。

塗り方のパターン数を求めるには、
そのマスが白の塗り方 = 全ての子の任意色の塗り方の積
そのマスが黒の塗り方 = 全ての子の白の塗り方の積
そのマスが任意色の塗り方 = そのマスが白の塗り方 + そのマスが黒の塗り方
で出せる。
黒か任意色かはどちらかだけ記録すれば十分。
（もちろん両方記録してもいい）

答えはmod10^9+7での値なので、剰余類環も参照。

解答例

解答例

注意点

別解