ABC 328 F — Good Set Query

考察

採用済みの条件から二つの変数の差が決まっているなら、新しい条件とはその値を比較すればよい。まだ差が決まっていなければ、一方の変数群をまとめて平行移動して新しい条件に合わせられる。この「差が決まる範囲」と「その範囲内での差」を、重み付き Union-Find で管理する。

連結性だけでは何が足りないか

条件 Xa−Xb=dX_a-X_b=d を頂点 a,ba,b を結ぶ辺と考える。採用済みの辺をたどれば差を足し合わせられるので、同じ連結成分内の二頂点の差は一意に決まる。例えば、

X1−X2=3,X2−X3=−1X_1-X_2=3,\qquad X_2-X_3=-1

を採用すると、X1−X3=2X_1-X_3=2 である。次の条件が X1−X3=2X_1-X_3=2 なら採用でき、X1−X3=4X_1-X_3=4 なら矛盾する。通常の Union-Find は両者をともに「連結」と判定するため、差の情報を補う必要がある。

一方、別々の連結成分なら、それぞれの成分内の全変数へ同じ整数を加えても既存の条件は変わらない。成分間の差にはまだ自由度があるため、初めて両成分を結ぶ条件は必ず採用できる。

毎回、採用済みの辺を DFS でたどって差を求める方法もあるが、一回に最大 O(N+Q)O(N+Q)、全体で O(Q(N+Q))O(Q(N+Q)) かかる。必要なのは、成分を併合しながら差を再利用する方法である。

親への差を持ち、経路圧縮でも保つ

各頂点 vv に対し、parent[v] を DSU 上の親、diff[v] を「子の値から親の値を引いた差」と定める。

diff[v]=Xv−Xparent[v]\mathrm{diff}[v]=X_v-X_{\mathrm{parent}[v]}

初めは全頂点が単独の成分なので、parent[v] = v、diff[v] = 0、根が持つ成分サイズ size[v] = 1 とする。DSU の親辺は差を表すための辺であり、入力された辺そのものとは限らない。

find(v) は根を返すと同時に経路を圧縮する。旧親を uu、成分の根を rr とすると、必要な更新は次の差の加算になる。

Xv−Xr=(Xv−Xu)+(Xu−Xr)X_v-X_r=(X_v-X_u)+(X_u-X_r)

そのため、旧親を保存し、その親の find を先に済ませてから差を加える。以下は擬似コードである。

find(v):
    if parent[v] == v:
        return v
    u = parent[v]
    r = find(u)
    diff[v] = diff[v] + diff[u]
    parent[v] = r
    return r

更新前の diff[v] は Xv−XuX_v-X_u、find(u) 後の diff[u] は Xu−XrX_u-X_r なので、圧縮後は diff[v] が根からの差 Xv−XrX_v-X_r になる。先に parent[v] を根へ書き換えると旧親を見失うため、この順序が必要である。

制約式から根の併合時の符号を導く

新しい条件 Xa−Xb=dX_a-X_b=d に対し、find(a)、find(b) を呼ぶ。得られた根を ra,rbr_a,r_b、圧縮後の差をそれぞれ pa,pbp_a,p_b とする。

pa=diff[a]=Xa−Xrapb=diff[b]=Xb−Xrb\begin{aligned} p_a&=\mathrm{diff}[a]=X_a-X_{r_a}\\ p_b&=\mathrm{diff}[b]=X_b-X_{r_b} \end{aligned}

同じ根なら根の値が打ち消され、Xa−Xb=pa−pbX_a-X_b=p_a-p_b である。従って pa−pb=dp_a-p_b=d のときだけ採用する。一致する条件は既存の差を言い直しているだけなので、採用しても DSU を併合し直す必要はない。

別の根なら常に採用できるが、親辺へ入れる値は式から求める。Xa=Xra+paX_a=X_{r_a}+p_a、Xb=Xrb+pbX_b=X_{r_b}+p_b を代入すると、

(Xra+pa)−(Xrb+pb)=d(X_{r_a}+p_a)-(X_{r_b}+p_b)=d

だから、rbr_b を rar_a の子にするときに必要な差は

Xrb−Xra=pa−pb−dX_{r_b}-X_{r_a}=p_a-p_b-d

となる。右辺を tt と置けば、併合方向ごとの更新は次のとおりである。

  • size[ra] >= size[rb] なら、parent[rb] = ra、diff[rb] = t として size[ra] に size[rb] を加える。
  • size[ra] < size[rb] なら、parent[ra] = rb、diff[ra] = -t として size[rb] に size[ra] を加える。

後者で必要なのは Xra−XrbX_{r_a}-X_{r_b} なので符号が反転する。tt は元の a,ba,b の向きで計算した値であり、根だけを交換して同じ値を代入してはいけない。

親単元の一般式は p[v]−p[u]=wp[v]-p[u]=w を扱う。本問では u=b,v=a,w=du=b,v=a,w=d と対応させれば同じ規約で使える。なお、個別公式解説は親差を「親−子」と定義しているため、本稿の diff とは符号が逆になる。式を参照するときは差の定義もそろえる。

三制約を実際に処理する

先ほどの例を、同サイズなら rbr_b を rar_a へ付ける規則で追う。

  1. X1−X2=3X_1-X_2=3:pa=pb=0p_a=p_b=0 なので t=−3t=-3。根2を根1へ付け、diff[2] = -3 とする。これは X2−X1=−3X_2-X_1=-3 を表す。
  2. X2−X3=−1X_2-X_3=-1:根は ra=1,rb=3r_a=1,r_b=3、差は pa=−3,pb=0p_a=-3,p_b=0。従って t=−3−0−(−1)=−2t=-3-0-(-1)=-2 であり、根3を根1へ付けて diff[3] = -2 とする。
  3. X1−X3=2X_1-X_3=2:同じ根で pa=0,pb=−2p_a=0,p_b=-2 なので、pa−pb=2p_a-p_b=2 が一致し採用する。親辺は追加しない。

併合の逆向きも確認しよう。1本目の直後に、2本目と等価な X3−X2=1X_3-X_2=1 を処理すると、ra=3,rb=1r_a=3,r_b=1、pa=0,pb=−3p_a=0,p_b=-3 だから t=0−(−3)−1=2t=0-(-3)-1=2 となる。今度は aa 側の成分が小さいので根3を根1へ付け、diff[3] = -t = -2 とする。条件の書き方が逆でも、同じ差に落ち着く。

続いて X1−X3=4X_1-X_3=4 は既存の差2と一致せず拒否する。その次に X3−X1=−2X_3-X_1=-2 が来れば採用できる。拒否した条件を基準へ混ぜなければ、後続の判定も元の採用集合に対して行える。

以上を質問の添字 i=1,2,…,Qi=1,2,\ldots,Q の順に実行し、採用したときだけ ii を答えの配列へ追加する。最後にその配列を空白区切りで出力すれば、既に昇順なのでソートは不要である。

典型の発動条件

weighted Union-Find

変数間の差分等式を順に追加し、その整合性や同一成分内の差を問い合わせるときに使う。連結性に加えて、親への差を経路圧縮で累積できることが要点である。全条件が最初から与えられる静的な問題なら、DFS・BFS による差の伝播も候補になる。

相対offsetの自由度

差だけを固定する等式では、各連結成分を独立に平行移動できる。別成分を結ぶ最初の等式はこの自由度を一つ使い、同成分を結ぶ等式は既存の差との一致を要求する。この二分が、オンラインの採用判定へつながる。

問題固有の要素

「良い集合か」という整数列の存在判定を、採用済みの条件の整合性として読む。整数列そのものを一つに決める必要はなく、成分内の差だけを保てばよい。差も併合時の調整量も整数なので、実数解しか存在しないという問題は起きない。

また、本問は矛盾した条件をその場で拒否する。矛盾を含むグラフ全体について後から問い合わせる問題とは異なり、管理中の成分は常に整合しており、成分に矛盾フラグを持たせる必要はない。

正当性

採用済みの条件は整合しており、DSU はその連結成分と、各頂点から親への差を正しく表しているとする。初期状態では条件がなく、この性質を満たす。経路圧縮は旧親までの差と旧親から根までの差を足すだけなので、表す差を変えない。

新しい条件の両端が同じ成分なら、既存の条件に沿って差を足した値は一意であり、それが根への差の差 pa−pbp_a-p_b に等しい。これが dd と一致すれば既存の解は新条件も満たす。一致しなければ既存の解のどれも新条件を満たせないので、拒否が必要である。

別成分なら、片方の全変数を同じ整数だけ平行移動しても既存の条件は保たれる。根の差を Xrb−Xra=pa−pb−dX_{r_b}-X_{r_a}=p_a-p_b-d に定めれば新条件を満たせる。逆向きの親辺にはこの符号反転を保存するので、どちらの併合方向でも全条件を満たす整数の割当てが存在し、親への差も正しく保たれる。

従って各質問で採用の可否を正しく判定し、採用後も不変条件を維持する。拒否時の経路圧縮も既存の差を保存するため、以後の判定に影響しない。採用した添字を処理順に出力するので、最終的な良い集合を昇順に得られる。

実装上の注意

  • find 後の diff[a]、diff[b] を使って pa,pbp_a,p_b を得る。圧縮前の親への差を、そのまま根への差として使わない。
  • 拒否した条件について併合やサイズ更新はしない。ただし、判定のために行った find の経路圧縮を巻き戻す必要はない。表現を変えただけで、採用済みの差は変わっていない。
  • a=ba=b なら差は必ず0であり、d=0d=0 のときだけ採用する。既存の条件と同じ条件も、矛盾しない限り別の添字として採用する。
  • 差は辺に沿って累積するので、入力の dd が32bit整数に収まっても、保持する差や tt の計算は符号付き64bit整数で行う。最大 N−1N-1 本の辺の和で差の絶対値は (N−1)×109(N-1)\times10^9 以下となり、32bitの範囲を超え得る。
  • 採用が一つもなければ、答えは空の行になる。公式入力例2の自己制約 X1−X1=1X_1-X_1=1 もこの場合である。

復習の核

  • 差の条件を辺と見たら、「同じ成分では差が確定し、別成分では平行移動が自由」と分けて考える。
  • 併合式を暗記せず、子−親という diff の定義を固定し、Xa−Xb=dX_a-X_b=d へ根と根への差を代入する。親子を逆に付ければ差の符号も逆になる。
  • 矛盾した条件の拒否と、DSU の内部表現を整える経路圧縮を区別する。巻き戻すべき制約追加は行わず、差を保存する圧縮はそのまま残せる。

計算量と制約

時間

初期化に O(N)O(N)。経路圧縮とサイズによる併合を使い、各質問で定数回の find と高々一回の併合を行うので、質問処理は全体で O(Qα(N))O(Q\alpha(N))(償却)、出力は O(Q)O(Q)。合計は O(N+Qα(N))O(N+Q\alpha(N))、通常の緩い表記では O((N+Q)α(N))O((N+Q)\alpha(N)) となる。α\alpha は逆アッカーマン関数である。

空間

親・親への差・成分サイズに O(N)O(N)、採用添字に最大 O(Q)O(Q) を使い、合計 O(N+Q)O(N+Q)。サイズによる併合では圧縮前でも木の高さは O(log⁡N)O(\log N) なので、再帰的な find のスタックもこの範囲に収まる。

制約との対応

公式制約は 1≤N,Q≤2×1051\leq N,Q\leq2\times10^5、1≤ai,bi≤N1\leq a_i,b_i\leq N、−109≤di≤109-10^9\leq d_i\leq10^9 で、入力はすべて整数である。質問ごとの全成分探索は避け、ほぼ定数の償却時間で処理する。累積差には符号付き64bit整数を使う。時間制限は2秒、メモリ制限は1024 MiBである。

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: potential・weighted DSU

主題
  • potential・weighted DSU: DSUの親辺にpotential差を持たせ、経路圧縮時の差の累積と根の併合方向に応じた符号を導出し、オンラインの差制約追加と頂点間差・矛盾のqueryを処理できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: potential・weighted DSU

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

      学習の位置

      体系上の位置: potential・weighted DSU

      • DSUの親辺にpotential差を持たせ、経路圧縮時の差の累積と根の併合方向に応じた符号を導出し、オンラインの差制約追加と頂点間差・矛盾のqueryを処理できる。

      先に読む単元:

      • DSUによる連結成分管理・縮約 — 辺追加や同値関係をDSUで統合し、成分代表と必要な成分metadataを一貫して保つ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。
      • 静的graph等式制約のpotential伝播 — 通常のDFS・BFSを土台に、辺等式からroot-relative potentialを静的に伝播し、cycle整合性と成分offsetの自由度を分離する。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題