完全永続 Union-Find

各頂点の親(根なら集合の大きさに $-1$ を掛けた値)を並べた配列を、 永続配列 と同じ考え方で持ちます。配列を二分木で表し、書き換えるときは根からその要素までの道のノードだけを複製するので、書き換える前の版もそのまま残ります。このファイルに永続配列(_get と _set)も入れてあるので、これだけで動きます。

経路圧縮をせず union by size だけを行うので、根にたどり着くまでに配列を読むのは $O(\log N)$ 回で、1 回読むのに $O(\log N)$ かかります。

版は番号で表し、初期状態が版 $0$ です。unite で新しい版ができるたびに、1 から順に番号を振ります。

クエリをすべて先読みできる問題なら、版を頂点、unite を辺とする木(版の木)を作って根から DFS し、辺を下るときにつなぎ、戻るときに取り消すようにすると、 ロールバック付き Union-Find で同じことができます。そちらの方が速く、メモリも少なくて済みます。

例:

uf = PersistentUnionFind(4)
v1 = uf.unite(0, 0, 1)  # 版 0 で 0 と 1 をつなぐ
v2 = uf.unite(v1, 2, 3)  # 版 v1 で 2 と 3 をつなぐ
v3 = uf.unite(v1, 1, 2)  # 版 v1 から枝分かれして 1 と 2 をつなぐ
print(uf.same(v2, 0, 3), uf.same(v3, 0, 2), uf.same(v3, 2, 3))  # False True False
print(uf.size(v2, 2), uf.size(v3, 0), uf.size(0, 0))  # 2 3 1
print(uf.unite(v3, 0, 2) == v3)  # True(すでに連結なので版は変わらない)

# i 番目のクエリ (k, a, b): ver[k] の版で a と b をつないだものを ver[i] とする(ver[0] は初期状態)
uf = PersistentUnionFind(n)
ver = [0] * (len(queries) + 1)
for i, (k, a, b) in enumerate(queries, 1):
    ver[i] = uf.unite(ver[k], a, b)

コード

class PersistentUnionFind:
    # 初期状態が版 0。unite は元の版を残したまま、新しい版の番号を返す
    # 各頂点の親(根なら -大きさ)を永続配列で持つ(union by size で経路圧縮はしない)
    def __init__(self, n):
        # 永続配列: 長さ 2^h の完全二分木。ノード o の子は C[o], C[o + 1](最下段では値)
        h = 1
        while (1 << h) < n:
            h += 1
        self.h = h
        C = [-1, -1]
        for _ in range(h - 1):
            C += [len(C) - 2] * 2  # 初めはすべて -1 なので、各段のノードは 1 つを共有する
        self.C = C
        self.roots = [len(C) - 2]  # roots[ver] = 版 ver の配列の根

    def _get(self, o, i):
        # 根が o の配列の i 番目
        C = self.C
        s = self.h - 1
        while s:
            o = C[o + (i >> s & 1)]
            s -= 1
        return C[o + (i & 1)]

    def _set(self, o, i, x):
        # 根が o の配列の i 番目を x にした配列の根を返す(i までの道のノードだけ複製する)
        C = self.C
        root = len(C)
        C.append(C[o])
        C.append(C[o + 1])
        o = root
        s = self.h - 1
        while s:
            k = o + (i >> s & 1)
            c = C[k]
            o = len(C)
            C[k] = o
            C.append(C[c])
            C.append(C[c + 1])
            s -= 1
        C[o + (i & 1)] = x
        return root

    def find(self, ver, x):
        # 版 ver での x の根
        o = self.roots[ver]
        p = self._get(o, x)
        while p >= 0:
            x = p
            p = self._get(o, x)
        return x

    def unite(self, ver, a, b):
        # 版 ver で a と b をつないだ新しい版の番号を返す(すでに同じ集合なら ver をそのまま返す)
        a = self.find(ver, a)
        b = self.find(ver, b)
        if a == b:
            return ver
        o = self.roots[ver]
        sa = self._get(o, a)
        sb = self._get(o, b)
        if sa > sb:
            a, b = b, a
        o = self._set(o, a, sa + sb)
        o = self._set(o, b, a)
        self.roots.append(o)
        return len(self.roots) - 1

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

    def size(self, ver, x):
        # 版 ver での x を含む集合の大きさ
        return -self._get(self.roots[ver], self.find(ver, x))