考察
木の頂点を選んだとき、親子を結ぶ辺の両端をともに選ぶ場合だけ、二つの連結成分が一つにつながる。この局所的な変化を使えば、部分木ごとに「成分数」と「根を選んだか」だけを覚えて、子の結果を併合できる。
頂点部分集合をすべて列挙し、各誘導部分グラフを探索する方法では、候補が 個ある。 では列挙できないので、同じ成分数になる選び方をまとめて数えたい。一方、連結な頂点集合だけを数えてから個数を掛け合わせる方法では、異なる集合どうしが隣接しないという条件を扱いにくい。そこで木に根を決め、辺一本で切り離せる子部分木から順に処理する。
選択頂点の誘導部分グラフは森なので、成分数は「選択頂点数 − 両端を選んだ辺の数」に等しい。親 と子 だけの2頂点で考えると、選び方は次の4通りである。
- 何も選ばない: 成分数は0。
- だけを選ぶ: 成分数は1。
- だけを選ぶ: 成分数は1。
- 両方を選ぶ: 頂点単体で数えた成分数の和は2だが、辺でつながるため1を引いて成分数は1。
子部分木が大きくなっても、親側との間にある辺は だけである。この辺で成分数を1減らすかどうかを決めるには、 を選んだかが分かればよい。成分の形や代表頂点を状態に持つ必要はない。
を、 を根とする部分木内で頂点を選び、誘導部分グラフの成分数が 、 の選択状態が となる選び方の個数とする。 は未選択、 は選択を表す。子を併合する途中では、同じ配列を「 と併合済みの子部分木」についての分布として使う。初めは 一つだけなので、 と 、それ以外は0である。
処理済みの親側の頂点数を 、次に併合する子 の部分木の頂点数を とする。成分数は頂点数を超えないので、親側の添字は 、子側は だけを回す。子の根の選択状態を とすると、新しい成分数は となる。ここで は両方が1のときだけ1、それ以外では0である。
成分数の添字を まで持つ新しい配列 を0で初期化し、各状態対について
と加算する。値が0の状態対は、添字を計算する前に飛ばす。特に なら有効な状態は なので、負の添字にはならない。全加算は を法として行う。併合が終わったら を に置き換え、処理済みサイズを に更新する。
子の計算を終えてから親へ返す順に、各子を一つずつ併合する。木全体の根を とすると、答えは を について出力すればよい。空集合も遷移に必要だが、成分数0の答えは出力しない。
典型の発動条件
境界状態付きtree DP
部分木から外へ出る辺が根と親を結ぶ一本だけなら、その辺での接続を決める根の情報を状態に残す。本問では根の選択状態だけで、併合時に成分がつながるかを判定できる。
二乗tree knapsack
互いに素な頂点集合を併合し、頂点数までの個数分布を二重ループで合成するときに使う。ループ範囲を実際の集合サイズへ絞ると、全併合の積の総和を頂点対へ対応付けて評価できる。詳しい数え方は「時間」で示す。
forestのc=n-m
森の連結成分数は頂点数から辺数を引いた値になる。頂点を選ぶと1増え、隣接する両端を選んだ辺ごとに1減る。この等式を使う前に、誘導部分グラフにも閉路がないことを確認する。
問題固有の要素
選択頂点が作る成分の形をすべて記憶すると状態が膨らむ。本問では元のグラフが木で、子部分木との境界が辺一本であることに注目すると、成分数と根の選択状態だけで次の併合を決められる。
正当性
選択頂点の誘導部分グラフは森である。併合する二つの頂点集合の間には親子の辺が一本だけあり、その両端を選ぶときだけ別々の連結成分がつながる。従って新しい成分数は であり、親側の根の選択状態 は変わらない。併合後の頂点部分集合は、親側と子側の選択へ一意に分解できるため、それぞれの個数の積を加算すれば漏れも重複もない。頂点一つの初期値からこの併合を繰り返すと、各部分木の分布が正しく求まる。最後に根の選択状態が0と1の場合を足すことで、各成分数の全個数を得る。
実装上の注意
- 成分数0を配列に残す。子部分木から何も選ばない場合も併合に必要であり、出力するときだけ を除く。 でも同じ初期値が使え、出力は1になる。
- 併合前の配列を読み、新しい配列へ書く。同じ配列への加算では、今回併合した子の選択を再び使うおそれがある。
- 併合ごとに実際のサイズ を使い、成分数の添字をそれぞれ 、 に限る。全併合で両方を まで回すと、二乗時間の評価は成立しない。
- 作業メモリを線形に抑えるなら、併合後の古い親配列と子配列を解放する。各頂点の完成配列をすべて保存する実装とは空間計算量が異なる。
- 剰余を取っていても、個数の積を計算する際の整数型の幅に注意する。
復習の核
- 2頂点の4通りの選び方から、辺の両端を選ぶ場合だけ成分数を1引く遷移を再現する。
- 子ごとに二重ループがあっても、各併合で初めて同じ塊になる頂点対を数えると、全体の計算量を評価できる。実際のループ範囲がその集合サイズに一致するかも確認する。
計算量と制約
時間
全体で 。隣接リストの構築と親子関係の決定は 、頂点単体の初期化と出力もそれぞれ である。残る併合の総時間を評価する。
サイズ の集合を併合するとき、成分数の添字対はゼロも含めて 個ある。根の選択状態の組合せは4通りなので、時間は である。両集合は空でなく だから、
より、一回の併合は と評価できる。
では、すべての併合にわたる の和はいくつか。各頂点を一つの塊として始め、子の併合を「互いに素な二つの塊を一つにする操作」として追う。この併合手順を二分木で表すと、葉は元の頂点、各内部節点は一回の併合になる。この二分木は入力の木そのものではない。
サイズ の塊の間には、片方から一頂点ずつ選ぶ順序なしの頂点対が 個ある。その各対は、この併合で初めて同じ塊に入る。それ以前は別々であり、それ以後は同じ塊のままなので、別の併合で再び数えることはない。最後には全頂点が一つの塊になるから、異なる二頂点の対はすべてちょうど一回数えられる。従って、
となる。子を併合する順序や木の形によらず、この総和は変わらない。例えば一本道を端から根付けた場合は 、星型の木を中心から根付けた場合は で、どちらも同じ和になる。一回の併合を一律に と見積もって、さらに子の数を掛ける必要はない。
新配列は根の選択状態ごとに 要素を確保・初期化する。この時間も より に収まり、全体は前処理・出力を含めて となる。 では併合はなく、初期化と出力だけで終わる。
公式解説は部分木サイズで添字を制限する二乗の木DPを示している。頂点対に対応付けた総和と、ゼロ添字・配列初期化まで含めた上界は、その計算量を確かめるための本書での補完である。
空間
併合後に使い終えた配列を解放する実装では、入力の隣接リストと深さ優先探索のスタックを含めて 。
親側の処理済み部分や、子側で計算中・計算済みの部分について、生存している配列が表す頂点集合を互いに素に保つ。それらのサイズの和は高々 なので、各配列をその集合サイズに比例する長さにすれば、配列の総要素数も となる。併合中だけ古い二配列と新配列が重なるが、増えるのは定数倍である。未処理の部分にはまだ大きな配列を確保せず、子の内容を親へ取り込んだら子配列を保持し続けないことが条件となる。
全頂点の完成配列を保存する実装では、一本道で部分木サイズの和が となり、最悪 の空間が必要になる。
制約との対応
なので、頂点部分集合の全列挙はできないが、全体で二乗時間の併合は実行できる。入力は木であるため、部分木間を結ぶ辺が一本だけであることと、誘導部分グラフが森であることを使える。制限時間は2秒、メモリ制限は1024 MiBであり、成分数の範囲を実サイズへ絞り、必要な配列だけを保持する。出力する個数は を法とする。
出典