EDPC V - Subtree

部分木

問題ページ解答例

考え方

ABCでいうと、F問題級。

いわゆる全方位木DPの問題だが、この問題は普通の木DPっぽい思考で解ける。

まず、適当な頂点を根として選び、根付き木にしておく。
この上で黒い頂点全体が連結になるように塗ると、塗った部分もまた根付き木のようになる。
このとき、各頂点について、以下の $2$ つを考える。

その頂点が、黒い頂点の根付き木の根になっている塗り方の個数 black_root[i]
その頂点が、黒い頂点の根付き木の葉になっている塗り方の個数 black_leaf[i]

すると、その頂点が黒く塗られるパターンは、この積で求められる。

まず、black_root[i] を葉側から求める。

自身が全体の葉だった場合は、$1$。
子がある場合、それぞれの子 j について、白い頂点にするか黒い頂点にするかをわけて考える。
すると、子 j からの寄与は black_root[j] + 1 である。
これを全ての子について掛け合わせれば、black_root[i] が求まる。

そして、black_leaf[j] を根側から求める。
自身が全体の根だった場合は、$1$。
そうではなかった場合の説明を親を i として以下に書く。

親 i より上側から来る寄与は black_leaf[i] である。
また、子 j 以外の子 x については、それぞれ black_root[x] + 1 通りの選び方がある。
したがって、black_leaf[j] は次のようになる。

black_leaf[j]
= 1 + black_leaf[i] * 子 j 以外の子 x についての (black_root[x]+1) の積

ただし、子を $1$ つ固定するたびに、他の子の積を愚直に取り直すと $O(N^2)$ になって遅い。
そこで、black_root[i] を作っているときに一工夫。
左からの累積積と右からの累積積を求めることで、(black_root[x]+1) の積 部分だけ求めてしまう。
すると、後からちゃんと計算するときに、そこに black_leaf[i] をかけて $+1$ するだけでよくなる。

これで black_root[i] と black_leaf[i] が求まったので、各頂点ごと積を取れば答え。

計算量は $O(N)$。

動作例

ここでは、説明用に次の独自入力例で考える。

0-indexed に直すと、辺は次のようになる。

頂点 0 を根とする根付き木として見る。

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

まず、葉側から black_root を求める。

頂点 2, 3, 4 は葉なので、子からの寄与はない。

black_root[2] = 1
black_root[3] = 1
black_root[4] = 1

頂点 1 には子 3, 4 がある。
それぞれの子について、使わない場合と使う場合がある。

black_root[1]
= (black_root[3] + 1) * (black_root[4] + 1)
= (1 + 1) * (1 + 1)
= 4

このとき、後で black_leaf を配るために、子を $1$ つ除いた積も累積積で求めておく。
子 3, 4 からの寄与は、それぞれ次の値である。

black_root[3] + 1 = 2
black_root[4] + 1 = 2

左からの累積積と右からの累積積を作る。

left:  {1, 2, 4}
right: {4, 2, 1}

これにより、それぞれの子を除いた積が $O(1)$ で求まる。

子 3 以外の積: left[0] * right[1] = 1 * 2 = 2
子 4 以外の積: left[1] * right[2] = 2 * 1 = 2

頂点 0 には子 1, 2 がある。

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

ここでも、子 1, 2 をそれぞれ除いた積を累積積で求めておく。
子 1, 2 からの寄与は、それぞれ次の値である。

black_root[1] + 1 = 5
black_root[2] + 1 = 2

左からの累積積と右からの累積積は次のようになる。

left:  {1, 5, 10}
right: {10, 2, 1}

したがって、それぞれの子を除いた積は次のようになる。

子 1 以外の積: left[0] * right[1] = 1 * 2 = 2
子 2 以外の積: left[1] * right[2] = 5 * 1 = 5

よって、black_root は次のようになる。

black_root: {10, 4, 1, 1, 1}

次に、根側から black_leaf を求める。

根 0 には親側がないので、次から始める。

black_leaf[0] = 1

頂点 0 から子 1 に値を渡す。
子 1 から見た親側には、兄弟である子 2 側の寄与が含まれる。
これは先ほど求めた、子 1 以外の積である。

black_leaf[1]
= 1 + black_leaf[0] * 子 1 以外の積
= 1 + 1 * 2
= 3

頂点 0 から子 2 に値を渡す。
子 2 から見た親側には、兄弟である子 1 側の寄与が含まれる。
これは先ほど求めた、子 2 以外の積である。

black_leaf[2]
= 1 + black_leaf[0] * 子 2 以外の積
= 1 + 1 * 5
= 6

次に、頂点 1 から子 3 に値を渡す。
子 3 から見た親側には、頂点 1 より上側の寄与と、兄弟である子 4 側の寄与が含まれる。
これは先ほど求めた、子 3 以外の積である。

black_leaf[3]
= 1 + black_leaf[1] * 子 3 以外の積
= 1 + 3 * 2
= 7

同様に、頂点 1 から子 4 に値を渡す。
ここでも、先ほど求めた子 4 以外の積を使う。

black_leaf[4]
= 1 + black_leaf[1] * 子 4 以外の積
= 1 + 3 * 2
= 7

よって、black_leaf は次のようになる。

black_leaf: {1, 3, 6, 7, 7}

最後に、それぞれの頂点について black_root[i] * black_leaf[i] を求める。

頂点 0: 10 * 1 = 10
頂点 1: 4 * 3 = 12
頂点 2: 1 * 6 = 6
頂点 3: 1 * 7 = 7
頂点 4: 1 * 7 = 7

よって、この入力例に対する出力は次である。

注意点

答えは m で割った余りを要求されているので、剰余類環の考えに従って処理する。
今回は法が $10^9+7$ 固定ではなく、入力で与えられる m である点に注意する。

別解

根付きにしないまま、各辺に「そこから先の部分木を、根を黒くして塗る方法」を持たせる実装もある。
深さ優先探索的に求めていくことになるが、「自身以外の積を求める」部分がかなり複雑になる。