ABC 295 G — Minimum Reachable City

考察

元の木の辺は親→子であり、親番号は子番号より小さい。追加クエリ1 u vは、uの祖先vへ戻る辺u→vを加える。元の木のv→uという子孫向きの道と合わせて閉路ができ、その道と交わる既存SCCが一つになる。Q回もSCC分解をやり直すO(Q(N+Q))は避け、成分が併合だけする性質を使いたい。

各SCCは元の木で連結な頂点集合であり、その中で最も浅い頂点が一つ存在する。以降これをtopと呼ぶ。祖先ほど番号が小さいのでtopは成分の最小番号でもある。SCCを縮約すると残る辺は子孫方向の木辺であり、外の成分へ進んでもそのtopの番号は増える。従って出力クエリ2 xの答えはx所属成分のtopになる。

DSUはunion by sizeで管理し、各代表rの属性top[r]に成分の最小番号を持つ。DSUの代表自体が木で最上位とは限らない。初期値はsingletonでtop[i]=i、parent[i+1]=p_iとする。

更新は子孫u側から祖先v側へ進める。find(u)≠find(v)の間、m=top[find(u)]、a=find(m)、b=find(parent[m])を求める。newTop=min(top[a],top[b])を保存し、r=merge(a,b)の後にtop[r]=newTopとする。改めてfind(u),find(v)を比較し、同成分になったら止める。この順なら消えた成分内部の道を一頂点ずつ歩かず、次の未併合境界だけへ進める。

例えば二頂点の木1→2に1 2 1を適用すると、m=2からparent[2]=1へ併合し、2 2には1を返す。逆にv=1から親をたどる方法では子孫2へ到達できない。枝分かれした成分が既にある場合も、成分全体を一度に併合してそのtopの親へ進む。追加辺の端点が既に同SCCならwhileは一度も実行しない。

典型の発動条件

DSUによる単調SCC併合

発動条件: 辺追加でSCCが分裂せず併合だけする。

連結成分と最小頂点をunionで維持する。

path compression jump

発動条件: 木path上の未併合境界を繰り返し越える。

吸収済み区間を代表値で飛ばし総移動を償却する。

問題固有の要素

p_i≤iにより頂点番号が木の祖先方向と対応し、SCC最小番号がpath探索のjump pointerを兼ねる。

別の問題へ持ち帰る視点: 単調併合問題では成分の極値を次の未処理位置として使う。

正当性

初期SCCはsingletonで、元の木上で連結かつtopが最小番号という不変条件を満たす。追加u→vが作る閉路は、元の子孫向きの道v→uと戻り辺からなる。既存の縮約木ではv所属成分からu所属成分までの道上成分が相互に到達可能になる。それ以外の成分へ出る辺は子孫向きで戻れないため、新たに同SCCへ入ることはない。

uとvが別成分の間、u側成分のtop=mはこの縮約道上にあり、parent[m]は道上の一つ上の成分に属する。これらを併合すると成分は木上で連結なまま、min(top[a],top[b])が新topとなる。既存の成分内部を飛ばしても必要な成分を漏らさず、同成分になった時点で閉路上の成分をちょうど吸収し終える。この間mは根ではないのでparent[m]の参照も合法である。

更新後の縮約木も親→子の向きで、成分topの番号は各辺で厳密に増える。従ってxから所属SCCのtopへ到達でき、外の到達成分にはそれより小さい番号がない。2 xへtop[find(x)]を返せば最小番号を得る。成功unionごとに成分数が一つ減るため、whileの全反復はN−1回以下である。

実装上の注意

  • 木辺v→uは子孫方向、更新走査uからvは親方向である。変数の大小だけでなく公式の祖先条件から始点を決める。
  • union前に両topの最小を保存し、unionが返した新代表へ書く。任意に選ばれるDSU代表のparentを参照せず、必ず成分topのparentを使う。
  • 停止条件はfind(u)=find(v)。v側成分のtopがvより上にある場合や、重複した追加でも余分に根へ進まない。

復習の核

  • 元の道の向きと、その道を縮約する走査の向きは逆になり得る。
  • 成分代表と、次の境界を指す成分属性を分ける。
  • 成分数の減少で全while回数を評価し、一クエリの長さをQ倍しない。

計算量と制約

時間

N頂点Q操作。吸収境界は高々N−1、DSU操作で O((N+Q)α(N))。

空間

親木、DSUと成分最小 O(N)。

制約との対応

公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 2\leq N \leq 2\times 10^5; 1\leq Q \leq 2\times 10^5; 1\leq p_i\leq i; For each query in the first format: 1\leq u,v \leq N. u \neq v. On G_S, vertex u is reachable from vertex v via some edges.; 1\leq u,v \leq N.; u \neq v.; On G_S, vertex u is reachable from vertex v via some edges.; For each query in the second format, 1\leq x \leq N.; All values in the input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Minimum Reachable City の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 単調path contraction・DSU jump

主題
  • 単調path contraction・DSU jump: 一度確定したpath区間を次未処理pointerまたはDSU parentで飛ばし、各頂点を高々一度だけ縮約する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
    • 単調進行による償却解析: 要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑えられる。
    • DSUによる連結成分管理・縮約: 静的な辺を探索して成分を付けるか、辺追加ごとに成分を併合し、同一成分・サイズを判定できる。

    主タグ: 単調path contraction・DSU jump

    補助タグ: 単調進行による償却解析 DSUによる連結成分管理・縮約

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

    学習の位置

    体系上の位置: 単調path contraction・DSU jump

    • 一度確定したpath区間を次未処理pointerまたはDSU parentで飛ばし、各頂点を高々一度だけ縮約する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    • 単調進行による償却解析 — 要素の一方向移動・一度だけの削除・軽辺へ進むたびの部分問題サイズ半減など、単調に減るpotentialから操作列全体の仕事量を抑える。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
    • DSUによる連結成分管理・縮約 — 辺追加や同値関係をDSUで統合し、成分代表と必要な成分metadataを一貫して保つ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題