EDPC P - Independent Set

独立集合

考え方

ABCでいうと、E問題級。

G問題の類似品。

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

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

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

計算量は $O(N)$。

次の入力例で考える。

入力を 0-indexed で受け取る。

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

頂点 0 を根とする根付き木にすると、子の関係は次のようになる。

children[0]: {1, 2}
children[1]: {3, 4}
children[2]: {}
children[3]: {}
children[4]: {}

トポロジカルソート順は根から葉への順番なので、これを逆順にして葉から根へ処理する。

order: {4, 3, 2, 1, 0}

white[v] を、頂点 v を白にして v 以下の部分木を塗る方法数とする。
black[v] を、頂点 v を黒にして v 以下の部分木を塗る方法数とする。

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

white[2] = 1
black[2] = 1
white[3] = 1
black[3] = 1
white[4] = 1
black[4] = 1

頂点 1 を見る。
子は頂点 3, 4 である。

頂点 1 を白にする場合、子はそれぞれ白でも黒でもよい。

white[1] = (white[3] + black[3]) * (white[4] + black[4])
         = 2 * 2
         = 4

頂点 1 を黒にする場合、子は全て白でなければならない。

black[1] = white[3] * white[4]
         = 1 * 1
         = 1

頂点 0 を見る。
子は頂点 1, 2 である。

頂点 0 を白にする場合、子はそれぞれ白でも黒でもよい。

white[0] = (white[1] + black[1]) * (white[2] + black[2])
         = (4 + 1) * (1 + 1)
         = 10

頂点 0 を黒にする場合、子は全て白でなければならない。

black[0] = white[1] * white[2]
         = 4 * 1
         = 4

根である頂点 0 の部分木は全体なので、答えは次のようになる。

white[0] + black[0] = 10 + 4 = 14

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

特になし。