ABC 223 G — Vertex Deletion

考察

頂点を削除しても最適値が変わらないなら、その頂点を使わずに最適値を達成できるはずだ。この存在判定を木の各方向から渡す白黒の状態へまとめ、全方位木DPで全頂点について求める。

マッチングとは、端点を共有しない辺の集合であり、その大きさは選んだ辺の本数である。グラフ HH の最大マッチングの大きさを μ(H)\mu(H)、元の木を TT と書く。頂点 vv を削除した森のマッチングは、元の木でもそのまま使える。逆に、元の木に vv を使わない最大マッチングがあれば、それを削除後の森へ残せる。従って、求める条件 μ(T−v)=μ(T)\mu(T-v)=\mu(T) は、「TT に vv を使わない最大マッチングが存在する」ことと同値である。

各頂点を削除して木DPをやり直すと O(N2)O(N^2) 時間かかるので、削除する頂点を根と見て、隣接する各方向の情報を再利用したい。

ここで、一つの最大マッチングを作り、使わなかった頂点を数えるだけでは足りない。中心と三つの葉からなる4頂点の星型では、最大本数は1である。どの葉を消しても辺は残るため、三つの葉は全て削除できる。一方、一つの最大マッチングで未使用なのは二つの葉だけである。判定対象ごとに、避けるための辺の選び方を変えてよいことが重要になる。

白黒を、辺を切った片側の状態として定義する

隣接頂点 u,vu,v に対し、辺 uvuv を切ってできる uu 側の木を Tu→vT_{u\to v} とし、uu をその根と見る。uu から vv へ渡す情報(有向メッセージ)を次のように定義する。

  • 白:Tu→vT_{u\to v} に、uu を使わない最大マッチングが存在する。
  • 黒:Tu→vT_{u\to v} のどの最大マッチングでも uu を使う。

白を1、黒を0として、値を wu→vw_{u\to v} と書く。白黒は、辺を切った側だけでの最適解の存在を表す。白い根が、後から切断辺を通じて相手と結ばれることはあるので、完成した一つのマッチングの使用フラグとして扱わない。

根と結んで1本増やせるのはどの側か

Tu→vT_{u\to v} で、uu 以外を各隣接側へ分ける。uu の隣接頂点集合を Adj⁡(u)\operatorname{Adj}(u) とし、次を基準値にする。

B=∑x∈Adj⁡(u)∖{v}μ(Tx→u)B=\sum_{x\in\operatorname{Adj}(u)\setminus\{v\}}\mu(T_{x\to u})

uu を使わない場合、各側の最大マッチングを独立に合わせられるので、最大本数はちょうど BB である。uu を使う場合も、uu から出る辺は高々1本しか選べない。その1本によって基準値より増えるかを調べる。

  • 白い側が一つでもある場合:その側の根を xx とする。白の定義から、xx を使わずにその側の最大本数を達成できる。そのマッチングに辺 uxux を加え、他の側の最大マッチングと合わせれば B+1B+1 本になる。どんなマッチングも各側で最大本数を超えられず、側を結ぶ辺は高々1本なので、これが全体の最大値である。uu を避けると BB 本に留まるため、u→vu\to v は黒になる。
  • 白い側が一つもない場合:uu と隣接頂点 xx を結ぶには、xx 側で xx を使わないようにする必要がある。しかし黒の定義から、その側では最大本数を達成できず、少なくとも1本減る。辺 uxux を加えても、その減少を取り戻すだけで BB 本を超えない。uu を使わずに BB 本を作れるので、それが全体の最大値となり、u→vu\to v は白になる。

これで、各側の最大本数を実際に保持しなくても、白い入メッセージがあるかだけで次の状態を決められる。

wu→v=1⟺∑x∈Adj⁡(u)∖{v}wx→u=0w_{u\to v}=1 \quad\Longleftrightarrow\quad \sum_{x\in\operatorname{Adj}(u)\setminus\{v\}}w_{x\to u}=0

葉から親へ送る場合は和の対象が空で、和は0である。葉だけの木の最大本数は0で、葉を使わずに達成できるから、白を送る。

判定したい頂点 uu を木全体の根にするときも、全ての隣接側に同じ議論を適用できる。全方向から来る白の個数を

Cu=∑x∈Adj⁡(u)wx→uC_u=\sum_{x\in\operatorname{Adj}(u)}w_{x\to u}

とすれば、Cu=0C_u=0 が、uu を削除しても最大本数が変わらないための必要十分条件である。

星型の例では、三つの葉から中心への値は全て1である。中心から各葉へは、他の二葉から白が来るので0を送る。従って中心は Cu=3C_u=3 で削除できず、各葉は Cu=0C_u=0 で削除できる。一つの最大マッチングを固定せず、三葉全ての存在判定ができている。

子から親、親から子の二走査で全方向を求める

計算のために頂点1を仮の根とし、親配列と「親が子より先に現れる訪問順」を作る。根以外の頂点 uu の親を p(u)p(u) と書き、次の順で処理する。

  1. 子から親へ:訪問順を逆にたどる。uu の全ての子 xx からの値 wx→uw_{x\to u} を足し、和が0なら wu→p(u)=1w_{u\to p(u)}=1、それ以外なら0とする。葉から順に、必要な値が揃った状態で計算できる。仮の根には親への送信を行わない。

  2. 親から子へ:訪問順をそのままたどる。uu に着いた時点では、子からの値に加え、根以外なら親からの値 wp(u)→uw_{p(u)\to u} も揃っている。これらを足して CuC_u を求め、0なら答えを1増やす。各子 xx へは、白の総数からその子自身の寄与を引いて

    wu→x=1⟺Cu−wx→u=0w_{u\to x}=1 \quad\Longleftrightarrow\quad C_u-w_{x\to u}=0

    と計算する。こうして親側の情報を次の頂点へ渡せる。

仮の根では親方向を足さず、子からの値だけで答えを判定する。送信先だけを除く集約は整数の引き算で作れるため、隣接方向を毎回数え直す必要はない。

典型の発動条件

木の最大マッチングの葉側貪欲

発動条件: 重みのない木のマッチングで、根を使う際の利益を、子側の最適値からの損失と比較できるとき。

白い子があれば、その子の根を避けた最適解と親子辺を選ぶ。白い子がなければ、根を使わず各子側の最適解を合わせる。この選び方で最大本数を達成できることが、貪欲法の根拠になる。辺に重みがある場合は「1本増えるか」という比較をそのまま流用できない。

全方位木DP

発動条件: 全ての根について木DPの答えが必要で、辺を切った片側の情報を一定サイズにまとめられるとき。

子から親、親から子へと情報を渡す。本問の合成は白の個数なので、送信先の寄与を引くだけで除外できる。一般の全方位木DPで使うprefix・suffixの合成を、この集約では単純な引き算で置き換えられる。

問題固有の要素

根を使わない場合の最大本数を基準にすると、根を使って増やせる本数は0か1だけになる。さらに、その増分は「最大本数を保って根を空けられる側があるか」で決まる。このため、最適値そのものを捨て、白黒一値だけを親へ渡せる。

状態を小さくしたいときは、親が子側の最適値の絶対値を必要とするのか、条件を付けたときの損失だけでよいのかを考える。

正当性

考察で示した二場合の最適値比較により、各隣接側の白黒が定義を満たせば、白い側がないとき、かつそのときに限って、根を避ける最大マッチングが存在する。葉からの白を出発点に、子から親への走査で全ての子側の状態が正しく求まる。親から子への走査では、既に求めた全入方向から送信先だけを除いて同じ規則を適用するため、親側の状態も正しく求まる。

従って、各頂点で全隣接方向を合わせた Cu=0C_u=0 は、その頂点を避ける最大マッチングの存在と同値である。冒頭の削除との同値性から、これを満たす頂点だけを数えれば答えになる。

最小の2頂点では、両方向のメッセージが白なので両頂点とも Cu=1C_u=1 となり、答えは0である。3頂点のパスでは中央から両端へ黒が送られ、両端だけが削除できる。4頂点のパスでは端からの状態が白・黒・白と交互に伝わり、どの頂点にも白い方向が一つあるため、削除できる頂点はない。

白黒の貪欲処理と全方位木DPは公式解説の方針であり、上の最適値の比較は、白が表す存在条件と遷移の必要十分性を説明するための補完である。

実装上の注意

  • 白黒を一度作ったマッチングの使用状態として更新しない。子から来た白は、その側の根を空ける最適解の存在を表す。
  • 白い入方向が一つだけなら、その方向へ送る値は白、他の方向へは黒になる。白い入方向が複数なら、どの一方向を除いても白が残り、送る値は全て黒になる。個数を単なる「白があるか」の真偽値へ潰すと除外できない。
  • CuC_u は頂点ごとに一度集計する。子ごとに全隣接方向を走査すると、星型の中心で O(N2)O(N^2) 時間かかる。
  • 長いパスでは再帰の深さが NN に達する。親配列と訪問順をスタックで作り、逆順・正順に処理すれば深い再帰を避けられる。

復習の核

  • 「削除しても最適値が同じ」は、その要素を使わない最適解の存在へ言い換える。一つの最適解で未使用だった要素の一覧だけでは判定しきれない。
  • 木DPの状態は、辺を切ったどちら側について、根にどの条件を課した値かを定義する。最後に作る解の使用フラグと混同しない。
  • 全方位木DPでは、全方向の集約から送信先だけを除く方法を先に考える。真偽だけでなく個数を持つことが、定数時間の除外につながる。

計算量と制約

時間

隣接リスト、親配列、訪問順の構築は O(N)O(N) 時間。二走査のそれぞれで各隣接リストを定数回走査し、有向辺 2(N−1)2(N-1) 本のメッセージを各 O(1)O(1) 時間で求める。全頂点の判定も含めて、合計 O(N)O(N) 時間である。

空間

隣接リスト、親配列、訪問順、各有向辺の白黒、白の個数を保持して、合計 O(N)O(N) 空間である。マッチングの具体的な辺集合や、各側の最大本数は保存する必要がない。

制約との対応

公式制約は 2≤N≤2×1052\leq N\leq 2\times 10^5、1≤ui<vi≤N1\leq u_i<v_i\leq N で、入力は全て整数、与えられるグラフは木である。時間制限は2秒、メモリ制限は1024 MiB。線形時間・空間なら上限に対応できる。辺を切ると両側が分離し、各側の最適解を独立に選べることに木の条件を使っている。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Vertex Deletion の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: rerooting・全方位木DP

主題
  • rerooting・全方位木DP: 子側と親側の寄与の差し替えを定義し、各頂点を根とした答えを求められる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: rerooting・全方位木DP

      執筆: abc-explanation-author1.1.1 / revision 3

      学習の位置

      体系上の位置: rerooting・全方位木DP

      • 子側と親側の寄与の差し替えを定義し、各頂点を根とした答えを求められる。

      先に読む単元:

      • 根付き木DP・部分木集約 — DPの最小十分状態で得た考え方と実装を再利用し、根付き木DP・部分木集約の発動条件・正当化・境界を重複なく学ぶ。

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題