ABC 460 G — Vertex Flip Query

考察

色を反転すると、その頂点の全ての隣接辺で「同色の頂点同士を結ぶか」が変わりうる。そこで辺を一本ずつ更新するのではなく、木の小さな部分ごとに、外との接点の色を仮定した表を持つ。接点が二つまでなら色の組合せは高々4通りである。実際の色を使う場所を各頂点に一つだけ設ければ、高次数の頂点の反転も一点更新にできる。

成分をたどる探索から、境界付きの表へ

操作3をそのまま実行するなら、照会頂点から同色の頂点だけを探索して重みを足せばよい。しかし道全体が同色なら毎回全頂点を訪れ、全体で O(NQ)O(NQ) かかる。色の異なる辺を切って連結成分を管理する方法も、星の中心の反転では一度に N−1N-1 本の辺が変わる。

一方、木のある部分と残りの木の間で、やり取りする情報は接点を通るものだけである。この部分をクラスタ、外との接点として残す頂点を境界と呼ぶ。境界は実際の接点より多く残してもよい。通常は0・1・2個に制限し、境界以外の頂点を内部頂点とする。辺を重複なく分割し、二つの子クラスタを一頂点だけで接合する分解を使う。共有頂点は必ず両方の子の境界に置き、内部頂点は子同士で重ならないようにする。

内部頂点の色・重みは現在の値を使うが、境界の色は変数として全割当を試し、境界自身の重みはまだ含めない。クラスタを KK、境界集合を BKB_K とし、各割当について次を保存する。

  • 境界頂点を、同色の道でつながるもの同士のグループに分ける。各グループに成分IDを付け、各境界がどのIDに属するか記す。
  • 各IDに、その成分に含まれる内部頂点だけの重み和を一つ保存する。同じIDを持つ境界が二つあっても、和の記録は一つである。

IDはその表の一項目の中だけで使う番号でよい。例えば各グループの最初の境界の添字をIDにすれば、別々の表での番号の一致を考えずに済む。色が同じというだけでは同じIDにしない。途中に異色の頂点があれば別成分である。

境界0個なら色割当は空の1通りで、保存する成分もない。境界1個なら色ごとに一つの成分と内部和を持つ。境界2個なら高々二つの成分を持つ。境界に一つも届かない閉じた成分は表から捨てる。外部とつながり直す道がないので、以後そのクラスタの外からの集計には寄与しない。その成分内の頂点自身を後から照会する方法は、後で別に構成する。

一回の合成で、何を一度だけ足すのか

道 a–w–ba\text{–}w\text{–}b、重み Wa=2,Ww=3,Wb=5W_a=2,W_w=3,W_b=5 を考える。二つの辺を子クラスタとし、親の境界を {a,b}\{a,b\} にする。両端の色を0と仮定し、実際の Cw=0C_w=0 を使うと、両端は同じ成分に属し、その内部和は3である。「aa 側の和3と bb 側の和3」を足すと6になってしまう。同じ成分IDの和3を一度だけ引き継ぐ必要がある。

同じ境界割当でも Cw=1C_w=1 なら、道の色は010になる。a,ba,b は同色だが別IDで、内部和はそれぞれ0である。ww の重み3は境界に届かない成分として捨てる。色000の場合にさらに両端を内部化すれば全体の和は 3+2+5=103+2+5=10 となるが、色010の場合に三頂点を一成分として足してはいけない。

一般の合成も、この処理を小さな連結成分の計算として行う。子を K1,K2K_1,K_2、共有頂点を ww、親に残す境界を BB とする。子の境界の和集合を U=BK1∪BK2U=B_{K_1}\cup B_{K_2} として、親の色割当ごとに次を行う。

  1. BB の頂点には割り当てた色を使う。U∖BU\setminus B の頂点は今回内部化するので、実際の色を使う。その色に対応する各子の表を一つずつ読む。
  2. UU の頂点を小さなグラフの頂点とする。同じ元頂点の ww は一つにまとめ、さらに各子の同じ成分IDに属する境界同士を結ぶ。定数個の頂点に対するUnion-Findや全探索で連結成分を求めればよい。
  3. 子ごと・成分IDごとに一度だけ、内部和を対応する小グラフの成分へ加える。二つの子でID番号が同じでも別の記録であり、両方を足す。同じ子の同一IDを境界ごとに繰り返し足してはいけない。
  4. 今回内部化する各頂点 z∈U∖Bz\in U\setminus B について、WzW_z をその頂点の成分へ一度加える。ww を境界に残すなら CwC_w はまだ変数で、WwW_w も足さない。
  5. 各成分と BB との共通部分を、新しい境界のグループにする。共通部分が空ならその成分を捨て、残るグループへ内部和と新しいIDを記録する。

接合後に境界を残す操作と、もう不要な境界を内部化する操作をこの手順でまとめて扱える。子が一つだけの場合も同じで、境界を取り除く際にその色を固定して重みを足す。通常の二分合成では ∣U∣≤3|U|\leq 3 なので、全色割当と成分の計算は定数時間で済む。

基底と、色・重みを固定する所有箇所

基底は一辺と、その両端を境界にしたクラスタである。色が等しければ両端を同じID、異なれば別IDにし、内部和は全て0とする。一頂点だけを境界にしたクラスタも内部和0で用意する。これらは実際の色・重みに依存しない。

この基底から通常の境界を高々二つに保つ分解を、Static Top Treeの単元の重み付きrake・compressで作る。本問の表へ接続する具体的な部品は次のように取れる。元の木に構築用の根を一つ決め、部分木サイズが最大の子をheavy、それ以外をlightとする。

  • light側の子 uu の部分木は、境界 {u}\{u\} で完成させておく。辺 vuvu と接合して uu を内部化すれば、境界 {v}\{v\} の枝になる。vv に付く枝同士は vv を残してrakeする。枝がなければ一頂点の基底を使う。
  • 各 vv の枝の束に、heavy側の次の頂点 hh がある場合は辺 vhvh を接合し、境界 {v,h}\{v,h\} の部品にする。heavy pathの末端では境界 {v}\{v\} のままにする。
  • heavy path上で隣り合う区間をcompressする。上区間の末尾境界と下区間の先頭境界として共有する ww を内部化し、区間全体の両端だけを残す。pathの末端まで含む区間では下側の境界がなくなり、path全体は先頭一頂点だけを境界に持つ。
  • 構築用の根まで処理したら、最後にその根も内部化し、境界0個の全体クラスタにする。

例えば一つのpath区間の境界は「区間の先頭」と「区間直後のheavy側の頂点」である。この取り方なら、隣接する区間はちょうど一つの境界を共有する。light側を完成させてから上へ進むことで、全辺を一度ずつ使える。

rakeの枝の重みはそのlight部分木の頂点数、compressの頂点部品の重みは「1+そこに付くlight部分木の頂点数の合計」とする。部品個数の中央で割るだけでは全体の高さが O(log⁡2N)O(\log^2 N) になることがある。単元で説明した累積重みの中央をまたぐ部品で分割する方法を使う。重み ss の部品から総重み SS の集合までの深さは O(1+log⁡(S/s))O(1+\log(S/s)) で、入れ子のサイズ比による対数の和とlight辺の通過回数から、合成木の高さは O(log⁡N)O(\log N) になる。上記の辺の接合などを加えても、一段当たり定数個の操作しか増えない。

各頂点 vv は、ある合成で境界から内部へ移り、それより上で再び通常の境界へ戻ることはない。その唯一の合成ノードを vv の所有ノードとして記録する。heavy pathの先頭(構築用の根を除く)なら親へ枝を接合する箇所、それ以外ならcompressで内部化する箇所、構築用の根なら最後に閉じる箇所が所有ノードになる。合成木の各ノードには子・親・境界集合と表を保存しておく。

操作1では CvC_v を反転し、操作2では WvW_v に与えられた値を加える。どちらも所有ノードを再計算し、その祖先だけを下から再計算する。所有ノードより下の全ての表では vv の色は変数、重みは未加算なので、隣接する辺の数にかかわらず更新不要である。星の中心でも、次数分の書換えは起きない。

内部に隠れた頂点から、照会を組み立て直す

通常の全体表には境界がなく、閉成分の情報も残らない。照会頂点 vv の所有ノードの通常表からも、内部化前の vv の情報を取り出せるとは限らない。所有ノードの子の表まで戻って合成をやり直し、今度は vv を境界として残す。 保存済みの表を書き換えず、照会用の作業表を一つ持って根へ運ぶ。

  1. 所有ノードを tt とする。vv は tt の子ではまだ境界にあり、子の表をそのまま使える。通常の親境界 BtB_t に vv を加えた集合を出力境界として合成する。これで CvC_v の固定と WvW_v の加算だけを先送りする。
  2. 親ノードへ一段上がる。今来た子の表を作業表に置き換え、もう一方の子には保存済みの通常表を使う。出力境界はその親の通常の境界集合に vv を加えたものとする。子が一つのノードなら、作業表だけを同じ規則で処理する。
  3. 根まで繰り返す。最終的な境界は {v}\{v\} だけになるので、色割当を実際の CvC_v に固定し、その成分の内部和に WvW_v を一度足して答える。

作業表の境界は「通常の高々二境界+照会頂点」の高々3個で、色割当は高々8通りである。接合途中に子の境界を合わせた小グラフは、高々4頂点になる。ここではまだ内部化していない共有頂点も含むため、保存する表の境界数と、合成途中の頂点数を区別する。どちらも定数であり、各段の処理は定数時間で済む。

道 a–w–ba\text{–}w\text{–}b の例で ww を照会するなら、ww を消した通常の {a,b}\{a,b\} 表は使わず、二辺の表から境界 {a,w,b}\{a,w,b\} の作業表を作る。色010でも、この時点では ww が境界なのでその成分を捨てない。上へ進んで a,ba,b を内部化しても、ww を含む成分は最後まで残り、答えは3になる。色000なら両端の重み 2+5=72+5=7 が同じ成分に入り、最後に Ww=3W_w=3 を加えて10になる。

通常表で閉成分を捨ててよいのは、その表を外部から利用する場合である。照会する vv は所有ノードより下では内部化されておらず、作業表ではそれ以降も境界に残る。したがって vv を含む成分が途中で捨てられることはない。兄弟の通常表から捨てた成分は、その兄弟の境界に届かず、vv へ接続することもない。これが、閉成分を全て保存せずに任意点照会を実現できる理由である。

個別公式解説は、Static Top Treeによる動的な全方位木DPと、根を変えたときに必要な両方向の情報を説明している。ここで用いた境界の全色割当・成分ID・頂点の所有箇所・追加境界による照会は、その方針を具体化する本書独自の表現である。ABC351 G公式解説の構築と接続し、以下の不変条件で正しさを確認する。公式問題文と両解説は2026-10-29に再照合した。

典型の発動条件

static top tree

発動条件: 固定された木で、一頂点の更新後に木全体や部分木のDP値を求めたいとき。

外との接点が少ない部分へ木を分け、接点から見える情報だけで合成できるかを考える。要約と合成が定数サイズなら、重みで平衡化した合成木を使って更新を O(log⁡N)O(\log N) にできる。辺の追加・削除まで含む問題には、この固定した分解をそのまま使えない。

動的rerooting DP

発動条件: 一点更新に加え、照会のたびに異なる頂点を根とする木DP値が欲しいとき。

固定した根へ向かう情報だけでは足りない。各境界から見える情報を持ち、照会頂点を境界に残して祖先方向の兄弟も合成できるかを調べる。本問では境界ごとの成分情報により、両方向を同じ表で扱える。

問題固有の要素

頂点の色は二値で、同色成分は境界の接続関係と内部和で要約できる。境界を二つに抑えると全色割当を保存できるため、色を実際の値に固定する場所を各頂点に一つだけ設けられる。

反転を「隣接辺が全て変わる操作」と捉えると高次数が障害になる。一段抽象化し、「未確定の境界色をどこで確定させるか」と考えることが、次数に依存しない更新への鍵である。色数や境界数が増える別問題では、全割当の数が許容範囲に収まるかを改めて確認する。

正当性

各表は、境界色を指定したときの同色連結成分を境界上へ制限した分割と、各成分の内部重み和を表す。一辺・一頂点の基底はこの定義を満たす。

子の内部頂点と辺は互いに重ならず、子をまたぐ道は共有境界を通る。したがって、子の成分内での接続と共有頂点の同一視で得る小グラフは、親の境界間にある同色の道を漏れなく、余分な接続なく表す。子の各成分の内部和を一度ずつ加え、内部化する頂点の重みだけを一度加えるので、合計にも重複や欠落はない。親境界に届かない成分は以後外部とつながらないため捨てられる。帰納的に通常表は定義を保つ。

実際の色・重みを表へ取り込むのは各頂点の所有ノード一箇所だけである。その頂点の更新によって変わりうるのは所有ノードと祖先の表に限られ、下からの再計算で全ての通常表が正しくなる。

照会は所有ノードの子から再構成するので、照会頂点が内部化された通常表を逆算しない。以降は照会頂点を境界へ残して同じ合成を行うため、その頂点を含む成分は捨てられず、作業表も同じ定義を保つ。根では全木を表し、唯一の境界である照会頂点と同色でつながる内部頂点の重みが得られる。その色を現在値に固定し、照会頂点自身の重みを足せば求める成分和になる。

実装上の注意

  • 境界の色は仮定値、重みは未加算とする。実際の値を辺の基底へ埋め込むと、高次数の頂点で一点更新が崩れる。
  • 同成分IDの内部和は子ごとに一度だけ足す。内部和が0でも、成分や接続が存在しないとは限らない。
  • 通常表は高々2境界、照会の作業表は高々3境界、合成途中は高々4頂点として領域を用意する。照会後も保存済みの通常表は変えない。
  • N=1N=1 では一頂点の基底を最後に内部化するノードが所有ノードになる。照会では内部化を先送りするだけで、常に現在の W1W_1 を返す。反復する反転や重み加算にも同じ手順を使える。
  • 入力の木は道になりうる。部分木サイズの計算など元の木をたどる処理には、明示的なスタックと逆順走査を使うと深い再帰を避けられる。合成木の高さとは別に注意する。
  • 初期重みと全加算の合計は高々 (N+Q)×109≤5×1014(N+Q)\times 10^9\leq 5\times 10^{14} なので、重み・成分和・出力は符号付き64bit整数で扱う。構築用の頂点数の重みと、更新される WvW_v を混同しない。色・重みの更新で分解自体を作り直す必要はない。

復習の核

  • 一点の変更が多数の辺へ波及するとき、接点の値を変数にした小さな表へ置き換えられないかを考える。
  • 境界ごとに同じ成分が見えるときは、和だけでなく成分IDを持つ。二つの見え方を二つの集合として足さない。
  • 捨てた内部成分を後から照会するには、消す前の部品へ戻って照会頂点を境界に残す。情報を捨てた表から復元しようとしない。
  • 更新時間の根拠は、要約の定数サイズと、頂点数の重みで保証した合成木の高さの両方である。

計算量と制約

時間

部分木サイズとheavy childの計算は O(N)O(N)。合成木は辺の基底・枝の束・path区間を合わせて O(N)O(N) ノードを持つ。単元で説明した累積重みと二分探索による構築を使い、その時間を O(Nlog⁡N)O(N\log N) と評価する。構築後に下から通常表を埋める費用は、一ノード定数時間なので O(N)O(N) である。

色の反転・重み加算は、所有ノードから根までの O(log⁡N)O(\log N) ノードを再計算する。任意点照会も同じ長さの経路で、各段につき高々一つの兄弟表を合成するので O(log⁡N)O(\log N)。N=1N=1 も含めて一操作 O(log⁡(N+1))O(\log(N+1))、前処理を含む全体は O(Nlog⁡(N+1)+Qlog⁡(N+1))O(N\log(N+1)+Q\log(N+1)) である。

公式解説は線形時間の構築を含む O(N+Qlog⁡N)O(N+Q\log N) を示しているが、ここでは線形構築を別途導かず、本文で用いる単元の構築時間を含めた上記の評価を採用する。

空間

元の木、部分木サイズ、各頂点の所有ノード、O(N)O(N) 個の合成ノードと各定数サイズ表で O(N)O(N)。照会の作業表は定数サイズで、祖先を順にたどるために木全体を複製する必要はない。

制約との対応

1≤N≤3×1051\leq N\leq 3\times 10^5、1≤Q≤2×1051\leq Q\leq 2\times 10^5。一操作で全頂点や全隣接辺を走査せず、合成木の対数段だけを処理する。通常の色割当は高々4通り、照会用でも高々8通りで、色数が2であることを定数サイズ性に使っている。

1≤Wi≤1091\leq W_i\leq 10^9、加算値も 1≤x≤1091\leq x\leq 10^9。和の上限は実装上の注意のとおり64bitに収まる。木の接続関係は全操作を通じて固定で、変わるのは一頂点の色または重みだけである。公式の実行時間制限は2秒、メモリ制限は1024 MiB。表は小さな固定長配列で表現でき、合成のために元のクラスタ内部を走査する必要はない。

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: rake・compressで動的木DPを保つ

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

    主タグ: Static Top Treeによる動的木DP

    補助タグ: rerooting・全方位木DP

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

    学習の位置

    体系上の位置: rake・compressで動的木DPを保つ

    • 境界頂点を持つtree clusterの要約と結合を定義し、局所更新後の木DP値を保てる。

    先に読む単元:

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

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

    • 更新を伴わない一回の木DP、および木上pathだけを列へ分けるHeavy-Light Decomposition。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題