EDPC P - Independent Set

独立集合

考え方

ABCでいうと、E問題級。

G問題の類似品。

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

塗り方のパターン数を求めるには、

で出せる。
黒か任意色かはどちらかだけ記録すれば十分。
もちろん両方記録してもいい。

計算量は $O(N)$。

入力を受け取る。

n: 5
edges:
  1 - 2
  1 - 3
  2 - 4
  2 - 5

頂点番号から $1$ を引き、0-indexed にする。

edges:
  0 - 1
  0 - 2
  1 - 3
  1 - 4

頂点 $0$ を根とすると、木は次の形になる。

0
├─ 1
│  ├─ 3
│  └─ 4
└─ 2

各頂点について、その頂点を白にした場合と黒にした場合の部分木の塗り方を考える。

葉である頂点 $2,3,4$ は、白でも黒でもそれぞれ $1$ 通りである。

次に頂点 $1$ の部分木を考える。
子は頂点 $3,4$ である。

頂点 $1$ を白にするなら、各子は白でも黒でもよい。
頂点 $3$ は $1+1=2$ 通りである。
頂点 $4$ も $2$ 通りである。
したがって、$2\times2=4$ 通りとなる。

頂点 $1$ を黒にするなら、子は全て白でなければならない。
したがって、$1\times1=1$ 通りとなる。

最後に、根の頂点 $0$ の部分木を考える。
子は頂点 $1,2$ である。

頂点 $0$ を白にするなら、各子は白でも黒でもよい。
頂点 $1$ の部分木は $4+1=5$ 通りである。
頂点 $2$ の部分木は $1+1=2$ 通りである。
したがって、$5\times2=10$ 通りとなる。

頂点 $0$ を黒にするなら、子は全て白でなければならない。
頂点 $1$ を白にする方法は $4$ 通りである。
頂点 $2$ を白にする方法は $1$ 通りである。
したがって、$4\times1=4$ 通りとなる。

根を白にする $10$ 通りと、黒にする $4$ 通りを足す。
答えは $10+4=14$ 通りである。

答えは $10^9+7$ で割った余りを要求されているので、剰余類環の考えに従って処理する。
掛け算や足し算をするたびに結果を % 1000000007 する。

特になし。