Day 105-Q2 | 永続Union-Find（Persistent DSU）

問題

$N$個の頂点に対し、時刻$1$から$M$にかけて$M$回のunion操作（$x_i$と$y_i$を連結にする）が行われる。unionは取り消されず、一度連結になった頂点対はそれ以降ずっと連結のままである。

すべてのunionを記録した後、$Q$個のクエリ$(p_j,q_j)$が与えられる。「時刻$0$から$M$のうち、$p_j$と$q_j$が初めて同じ連結成分に属する最小の時刻$t$」を答えよ。時刻$M$でも非連結なら$-1$。

連結性は時刻について単調（一度連結になれば戻らない）なので二分探索が使える。経路圧縮を行わずunion by sizeのみを使うと、各頂点の親は生涯高々1回しか変化しない（子になった頂点が再び親候補に選ばれることはない）ことが証明でき、この性質を使った「永続Union-Find」で$O(\log N)$の`find(x,t)`が実現できる。

入力形式

N M
x_1 y_1
...
x_M y_M
Q
p_1 q_1
...
p_Q q_Q

制約

$1 \le N \le 2\times10^5$

$0 \le M \le 2\times10^5$

$1 \le Q \le 2\times10^5$

$1 \le x_i,y_i,p_j,q_j \le N$

入出力例

入力例1

出力例1

時刻1:$\{1,2\}$。時刻2:$\{3,4\}$。時刻3で合体し$\{1,2,3,4\}$。時刻4で$\{5\}$が合流。頂点6はどのunionにも登場しないため常に非連結。

概念図: 親の変化は生涯1回だけ

ヒント（段階的開示）

ヒント1: 方向性

時刻$t$ごとにUnion-Findを毎回作り直すのは重い。union操作は取り消されないため「一度連結になった2頂点は未来永劫連結」という単調性がある。この単調性をどう二分探索に活かせるか考えよう。

ヒント2: アプローチ

経路圧縮を行わないUnion by Sizeを考える。あるノード$y$が別のノード$x$の子になったら、$y$は以後二度と根として union の対象にならない（union は常に現在の根同士を比較するため）。つまり各ノードの親の変化は生涯1回だけ。各ノードに「(変化時刻, 変化後の親)」を1つだけ記録すれば、`find(x,t)` は変化時刻が$t$以下ならその親へ移動する操作の繰り返しで実現できる。

ヒント3: 誘導（コード骨格）

change = [None] * n  # (time, new_root)

def find(x, t):
    while change[x] is not None and change[x][0] <= t:
        x = change[x][1]
    return x

for time in range(1, m + 1):
    x, y = unions[time - 1]
    rx, ry = find(x, time - 1), find(y, time - 1)
    if rx == ry:
        continue
    if size[rx] < size[ry]:
        rx, ry = ry, rx
    change[ry] = (time, rx)
    size[rx] += size[ry]
# クエリ: 非連結なら-1、連結なら0..Mで二分探索

模範解答 (Python)

import sys


def solve():
    data = sys.stdin.buffer.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    m = int(data[idx]); idx += 1

    unions = []
    for _ in range(m):
        x = int(data[idx]) - 1; idx += 1
        y = int(data[idx]) - 1; idx += 1
        unions.append((x, y))

    q = int(data[idx]); idx += 1
    queries = []
    for _ in range(q):
        p = int(data[idx]) - 1; idx += 1
        qq = int(data[idx]) - 1; idx += 1
        queries.append((p, qq))

    size = [1] * n
    change = [None] * n  # (time, new_root)

    def find(x, t):
        while change[x] is not None and change[x][0] <= t:
            x = change[x][1]
        return x

    for time in range(1, m + 1):
        x, y = unions[time - 1]
        rx = find(x, time - 1)
        ry = find(y, time - 1)
        if rx == ry:
            continue
        if size[rx] < size[ry]:
            rx, ry = ry, rx
        change[ry] = (time, rx)
        size[rx] += size[ry]

    out = []
    for p, qq in queries:
        if find(p, m) != find(qq, m):
            out.append(-1)
            continue
        lo, hi = 0, m
        while lo < hi:
            mid = (lo + hi) // 2
            if find(p, mid) == find(qq, mid):
                hi = mid
            else:
                lo = mid + 1
        out.append(lo)

    print('\n'.join(map(str, out)))


solve()

計算量: 構築$O(M\log N)$、各クエリ$O(\log N\log M)$（二分探索×find）。ランダム200ケースで愚直な時刻別DSU再構築との一致を確認済み。

Step-by-Step 解説

1経路圧縮なしのUnion by Size
経路圧縮すると親が何度も書き換わり永続性が崩れる。union by sizeのみで木の高さを$O(\log N)$に抑える。

2親の変化は生涯1回
一度子になった頂点は二度と根として union の対象にならないため、`change[y]`は1エントリだけで足りる。

3時刻を指定したfind
`find(x,t)`は変化時刻が$t$以下の間だけ親へ移動を繰り返す。$t$より後の変化は無視される。

4二分探索による時刻特定
連結性は$t$について単調なので、$0$〜$M$で二分探索して初めて連結になる時刻を特定する。

よくあるミス

ミス	原因	正しい書き方
`find`内で経路圧縮を実装する	親が複数回書き換わり「生涯1回」の前提が崩れる	経路圧縮は行わず union by size のみで高さを抑える
union時に`find(x,time)`（現在時刻含む）を使う	未処理の未来の変化を誤って参照する可能性	`find(x,time-1)`で直前までの状態を明示的に参照する
クエリで連結判定を省略し二分探索だけ行う	非連結な組では`lo`が$M$に収束し`-1`を返せない	先に`find(p,M)!=find(q,M)`を確認する
`change`が複数回設定される実装にしてしまう	永続性の前提（1回だけ）が崩れる	union by sizeの性質上1回しか設定されないことを利用する

次のステップ

発展: union操作にコストが伴う場合、時刻$t$までの累積コストクエリに答える
発展: Kruskal再構成木を使えばLCAのノード時刻を求める問題として$O((N+M)\log N)$前処理・各クエリ$O(\log N)$で解ける。両者を比較しよう
次回予告: 双調巡回セールスマン問題（Bitonic TSP・$O(N^2)$DPによる厳密解法）

自己評価

完全理解おおむね理解要復習

Day 105-Q2 — 永続Union-Find（Persistent DSU）

問題