部分永続 Union-Find

経路圧縮をせず union by size だけを行うと、根でなくなった頂点の親はその後ずっと変わりません。そこで、各頂点が根でなくなった時刻を覚えておくと、時刻 $t$ での根は、根でなくなった時刻が $t$ 以下である間だけ親をたどれば求まります。集合の大きさは、各根について、大きさが変わった時刻と変わった後の大きさの履歴を持っておき、二分探索で求めます。

unite を $t$ 回呼んだ直後を時刻 $t$ とします(初期状態が時刻 $0$)。すでに同じ集合にある 2 頂点を unite しても、時刻は 1 進みます。過去の状態は聞けるだけで、過去の状態から unite することはできません(それには 完全永続 Union-Find を使います)。

時刻 $t$ は $0$ 以上 now() 以下で指定します。

辺を 1 本ずつ加えていくとき、「 $a$ と $b$ が初めて連結になった時刻」は、same(t, a, b) が $t$ について単調(一度連結になればその後もずっと連結)なので、 $t$ についての二分探索で $O(\log Q \log N)$ で求められます( $Q$ は unite の回数)。クエリを先読みしなくても、聞かれるたびに答えられます。「 $x$ を含む集合と $y$ を含む集合を合わせて $z$ 頂点以上になる最初の時刻」のように、size を使う条件でも同じです。

例( $i$ 本目の辺を加えた直後が時刻 $i$):

uf = PartiallyPersistentUnionFind(n)
for u, v in edges:
    uf.unite(u, v)

def first_time(ok):
    # ok(t) が真になる最初の時刻(ok は t について単調。最後まで偽なら -1)
    if not ok(uf.now()):
        return -1
    lo, hi = -1, uf.now()
    while hi - lo > 1:
        mid = (lo + hi) // 2
        if ok(mid):
            hi = mid
        else:
            lo = mid
    return hi

# a と b が初めて連結になった時刻
print(first_time(lambda t: uf.same(t, a, b)))

# x を含む集合と y を含む集合を合わせて z 頂点以上になる最初の時刻
def total(t):
    if uf.same(t, x, y):
        return uf.size(t, x)
    return uf.size(t, x) + uf.size(t, y)

print(first_time(lambda t: total(t) >= z))

コード

from bisect import bisect_right


class PartiallyPersistentUnionFind:
    # unite を t 回呼んだ直後を時刻 t とする(初期状態は時刻 0)
    # union by size で経路圧縮をしないので、根でなくなった頂点の親はその後変わらない
    def __init__(self, n):
        self.t = 0  # 今の時刻
        self.par = [-1] * n  # 根でなくなったときにつないだ先
        self.tm = [1 << 60] * n  # tm[x] = x が根でなくなった時刻(根のままなら大きな値)
        self.st = [[0] for _ in range(n)]  # 根 x の大きさの履歴: 時刻 st[x][i] から大きさ sz[x][i]
        self.sz = [[1] for _ in range(n)]

    def now(self):
        # 今の時刻(unite を呼んだ回数)
        return self.t

    def find(self, t, x):
        # 時刻 t での x の根
        tm, par = self.tm, self.par
        while tm[x] <= t:
            x = par[x]
        return x

    def unite(self, a, b):
        # 時刻を 1 進めて a と b をつなぐ。すでに同じ集合なら False(このときも時刻は進む)
        a = self.find(self.t, a)
        b = self.find(self.t, b)
        self.t += 1
        if a == b:
            return False
        sa, sb = self.sz[a][-1], self.sz[b][-1]
        if sa < sb:
            a, b = b, a
        self.par[b] = a
        self.tm[b] = self.t
        self.st[a].append(self.t)
        self.sz[a].append(sa + sb)
        return True

    def same(self, t, a, b):
        # 時刻 t で a と b が同じ集合にあるか
        return self.find(t, a) == self.find(t, b)

    def size(self, t, x):
        # 時刻 t での x を含む集合の大きさ(履歴を二分探索する)
        x = self.find(t, x)
        return self.sz[x][bisect_right(self.st[x], t) - 1]