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)$。

具体例での動作

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

頂点番号から $1$ を引き、頂点 $0$ を根とする。

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

まず各頂点について、その頂点を黒くして、子側へ連結な黒い部分を伸ばす方法数を考える。

葉である頂点 $2,3,4$ では、子側に追加できる頂点がないので、それぞれ $1$ 通りである。

頂点 2: 1
頂点 3: 1
頂点 4: 1

頂点 $1$ では、子 $3,4$ について、その子側を使わないか、子を黒くして連結部分を伸ばすかを選べる。

各子からの選択肢は $1+1=2$ 通りである。
したがって、頂点 $1$ の子側の選び方は $2\times2=4$ 通りとなる。

頂点 $0$ では、子 $1$ から $4+1=5$ 通り、子 $2$ から $1+1=2$ 通りの選択肢がある。

したがって、頂点 $0$ の子側の選び方は $5\times2=10$ 通りとなる。

まとめると次のようになる。

頂点	子側の選び方
$0$	$10$
$1$	$4$
$2$	$1$
$3$	$1$
$4$	$1$

次に、各頂点から見た親側の選び方を考える。

根 $0$ には親側がないので $1$ 通りとする。

子 $1$ から親側を見る。
親 $0$ を白にして、親側を全く使わない方法が $1$ 通りある。

親 $0$ を黒にする場合は、さらに兄弟 $2$ の側を使わないか使うかを選べる。
兄弟 $2$ 側は $1+1=2$ 通りである。

したがって、頂点 $1$ の親側は $1+1\times2=3$ 通りとなる。

同様に頂点 $2$ では、兄弟 $1$ 側に $4+1=5$ 通りの選択肢がある。
したがって、親側は $1+1\times5=6$ 通りとなる。

頂点 $3$ から親側を見る場合を考える。
親 $1$ を白にする方法が $1$ 通りある。

親 $1$ を黒にする場合、頂点 $1$ より上側には $3$ 通りの選び方がある。
さらに兄弟 $4$ 側には $1+1=2$ 通りの選択肢がある。

したがって、頂点 $3$ の親側は $1+3\times2=7$ 通りとなる。
頂点 $4$ も同様に $7$ 通りである。

頂点	親側の選び方
$0$	$1$
$1$	$3$
$2$	$6$
$3$	$7$
$4$	$7$

この親側の計算では、子を $1$ つ除いた他の子からの寄与の積が必要になる。

例えば頂点 $0$ の子からの寄与は $5,2$ である。
子 $1$ を除く積は $2$、子 $2$ を除く積は $5$ となる。

子が多い場合でも毎回掛け直さないように、各頂点で左からの累積積と右からの累積積を作る。
これにより、任意の子を除いた積を $O(1)$ で求められる。

最後に、各頂点について子側の選び方と親側の選び方を掛ける。

頂点 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 である点に注意する。

別解

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