Day 157-Q3 — 分岐永続化Union-Find（Branching Persistent DSU）

問題

$N$ 頂点の Union-Find があり、バージョン $0$ は全頂点が孤立している。以下の $Q$ 個の操作を処理する。

• union b x y: バージョン $b$ を元に $x,y$ を併合した新しいバージョンを作る。バージョン $b$ 自身はこの後も不変
• query v x y: バージョン $v$ で $x,y$ が同じ連結成分か判定

union の b はどのバージョンからでも自由に選べるため、履歴は一直線ではなく分岐する版数の木になる。

入力形式

N Q
op_1
...
op_Q

制約

入出力例

8 8
union 0 0 1
union 0 2 3
union 1 1 2
union 2 1 2
query 1 0 1
query 1 2 3
query 3 0 2
query 4 1 3

Yes
No
Yes
Yes

概念図：v0から分岐する版数の木

ヒント（段階的開示）

# 添字0..N-1上の不変な二分木。1点更新は根から葉までの経路だけ新規作成
def set_(root, lo, hi, i, new_val):
    if lo == hi:
        return Node(val=new_val)
    mid = (lo + hi) // 2
    if i <= mid:
        return Node(left=set_(root.left, lo, mid, i, new_val), right=root.right)
    else:
        return Node(left=root.left, right=set_(root.right, mid+1, hi, i, new_val))

模範解答 (Python)

📋 コピーimport sys

class PersistentArray:
    class Node:
        __slots__ = ("val", "left", "right")
        def __init__(self, val=None, left=None, right=None):
            self.val, self.left, self.right = val, left, right

    def __init__(self, init_values):
        self.n = len(init_values)
        self.root = self._build(0, self.n - 1, init_values)

    def _build(self, lo, hi, vals):
        if lo == hi:
            return self.Node(val=vals[lo])
        mid = (lo + hi) // 2
        return self.Node(left=self._build(lo, mid, vals),
                          right=self._build(mid + 1, hi, vals))

    def get(self, root, i):
        lo, hi, node = 0, self.n - 1, root
        while lo != hi:
            mid = (lo + hi) // 2
            if i <= mid:
                node, hi = node.left, mid
            else:
                node, lo = node.right, mid + 1
        return node.val

    def set(self, root, i, new_val):
        def rec(node, lo, hi):
            if lo == hi:
                return self.Node(val=new_val)
            mid = (lo + hi) // 2
            if i <= mid:
                return self.Node(left=rec(node.left, lo, mid), right=node.right)
            return self.Node(left=node.left, right=rec(node.right, mid + 1, hi))
        return rec(root, 0, self.n - 1)


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

    parent_arr = PersistentArray(list(range(n)))
    size_arr = PersistentArray([1] * n)
    versions = {0: (parent_arr.root, size_arr.root)}
    next_id = 1

    def find(version, x):
        proot, _ = versions[version]
        while True:
            p = parent_arr.get(proot, x)
            if p == x:
                return x
            x = p

    out = []
    for _ in range(q):
        cmd = data[idx]; idx += 1
        if cmd == 'union':
            b = int(data[idx]); x = int(data[idx+1]); y = int(data[idx+2]); idx += 3
            proot, sroot = versions[b]
            rx, ry = find(b, x), find(b, y)
            if rx == ry:
                versions[next_id] = (proot, sroot)
            else:
                sx, sy = size_arr.get(sroot, rx), size_arr.get(sroot, ry)
                if sx < sy:
                    rx, ry = ry, rx
                    sx, sy = sy, sx
                proot2 = parent_arr.set(proot, ry, rx)
                sroot2 = size_arr.set(sroot, rx, sx + sy)
                versions[next_id] = (proot2, sroot2)
            next_id += 1
        else:
            v = int(data[idx]); x = int(data[idx+1]); y = int(data[idx+2]); idx += 3
            out.append("Yes" if find(v, x) == find(v, y) else "No")
    print('\n'.join(out))

solve()

Step-by-Step 解説

迷った他案と採らなかった理由

よくあるミス

次のステップ

• 発展: バージョン木上のLCAで「2つのバージョン間で共通するunion操作の接頭辞」を高速特定
• 発展2: サイズでなくランクベースのunionにした場合の高さの違いを比較
• 扱わなかった範囲: 経路圧縮つき永続Union-Findのならし計算量
• 次回予告: 経路圧縮つき永続Union-Findの検討

自己評価

自分の回答

気づき・メモ