ABC 453 F — Avoid Division

考察

辺を切った両側に同じ色が残る必要がある。特に元の葉を切り離す辺では、その葉の色をほかの頂点にも使わなければならない。N≥3、元の葉数 L に対し Σ_{C_i≥2}C_i≥L が必要である。

採用する候補: 元の葉を重み 1 とする centroid X を選び、X 削除後の成分ごとに葉を group 分けして、異なる group に同色を置く。

X は非葉で、各 group の葉数は L/2 以下。未着色葉総数 R に対し最大 group 数≤⌈R/2⌉ を保ちながら塗れば、R≥2 で異なる二 group を選べる。

棄却する候補: 色容量だけを見て任意の頂点から塗る。

同じ色を近い側に集めると、辺切断後の反対側に同色が残らない。容量条件を各 cut の witness へ結びつける必要がある。

N=2 は容量 2 以上の色があれば両頂点に使う。N≥3 は必要条件を確認し、容量 2 以上の各新色について次を行う。R=0 なら終了。R=1 なら最後の葉と X をその色にする。R≥2 なら最大の異なる二 group から一葉ずつ同色にし、残り容量 C_i−2 は毎回最大 group の葉へ使う。色の途中で R=1 になった場合は、その葉も今の色でよく、既に別 group の同色 partner がいる。未着色の内部頂点を余剰容量で埋める。

典型の発動条件

重み付き centroid による均衡分割

発動条件: 木の葉を複数 group に分け、どの group も半数を超えない中心が欲しいとき。

部分木葉数で centroid を選び、削除後成分を group 化する。

最大groupを均す貪欲

発動条件: 同じ色を少なくとも二groupへ配置しながら全要素を消費したいとき。

残数上位の異なるgroupから先に一つずつ取る。

問題固有の要素

全 edge cut 条件は、各葉の色が中心の反対側にも現れるという強い十分条件を構成すれば一括保証できる。

別の問題へ持ち帰る視点: 均衡 centroid と最大 heap を組み合わせると、異groupからpairを取り続けられる不変量を維持できる。

正当性

必要性は各元の葉がほかの頂点と同色でなければならないことから従う。葉重み centroid X は各削除成分の葉数を L/2 以下にできる。N≥3 では葉は centroid にならないので X は葉 group の外にある。

最大 group 数≤⌈R/2⌉ を不変量とする。初期に成立する。R≥2 なら最大 group は R より小さく、異なる二 group が存在する。最大の二 group から一葉ずつ取った後も最大数≤⌈(R−2)/2⌉。これは R が偶数なら上限に達する group が高々二つ、奇数なら厳密最大の group が高々一つなので、上限を下げる際にそれらを必ず減らせるためである。その後、最大 group から一葉ずつ取る操作も最大数≤⌈(R−1)/2⌉ を保存する。よって二葉からの新色開始は詰まらない。

各色で最初の二葉は別 group にある。その後どの group の葉に同色を追加しても、最初の二葉の一方は別 group にある。新色開始時に最後の一葉だけなら、容量 2 以上のその色で X も塗り partner を作る。容量条件から全葉を処理する前に eligible な色が尽きることはない。

任意の辺について X を含まない側には元の葉が少なくとも一つ存在し、その葉は一つの X 削除 group に属する。この葉の同色 partner は別 group または X なので辺の反対側にある。従って全辺の条件を満たす。残った内部頂点は ΣC_i≥N により余剰容量で塗れ、既存 partner の性質を壊さない。

実装上の注意

  • centroid は頂点数でなく元の葉数で求める。DFS の葉重み総和から各削除成分の重みを調べる。
  • 二葉を取る際は heap から異なる二 group を先に取り出し、減らしてから戻す。追加の葉は毎回現在の最大 group から取る。
  • X を使うのは新色開始時に未着色葉が一枚の場合。今の色を配っている途中で一枚になれば、その色で葉だけを塗ってよい。
  • N=2 は別処理する。残容量を減らしてから内部頂点を埋める。

復習の核

  • 未着色総数 R と最大 group 数≤⌈R/2⌉ の不変量で貪欲を証明する。同色 partner が各辺の反対側にいることを、葉 group と X の位置から説明する。

計算量と制約

時間

O(N log N)、葉group最大heapと色容量配分。

空間

O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1\leq T\leq 10^5; 2\leq N\leq 3\times 10^5; 1\leq K\leq N; 1\leq U_i,V_i\leq N; The given graph is a tree.; 1\leq C_i\leq N; C_1+C_2+\cdots+C_K\geq N; All input values are integers.; The sum of N over all test cases does not exceed 3\times 10^5.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Avoid Division の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 成立証明から構成解を復元する

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 構成解・witness復元

    補助タグ: 貪欲法と交換論 木の均衡分離点と重心分解

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

    学習の位置

    体系上の位置: 成立証明から構成解を復元する

    • 成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。

    先に読む単元:

    この解説で扱わないこと:

    • 存在判定・個数計算だけで、具体的な解や操作列を復元しない問題。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題