Day 088-Q2 — Euler Tour Tree（オイラーツアー木・動的森の連結性判定）

問題

$N$ 頂点からなる森（最初は辺なし）に対して $Q$ 個のクエリを処理せよ。1 u v: 辺追加（異なる成分保証）、2 u v: 辺削除（存在保証）、3 u v: 連結性判定。

入出力例

5 6
1 0 1
1 1 2
3 0 2
2 1 2
3 0 2
3 1 4

Yes
No
No

概念図: Euler ツアーを列として管理し reroot で回転

ヒント

def reroot(v):
    splay(v)
    L = v.left
    if L:
        L.parent = None
        v.left = None
    return merge(v, L)

模範解答

import sys

class Node:
    __slots__ = ('key', 'parent', 'left', 'right')
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.left = None
        self.right = None

def rotate(x):
    p = x.parent
    g = p.parent
    if p.left is x:
        p.left = x.right
        if x.right: x.right.parent = p
        x.right = p
    else:
        p.right = x.left
        if x.left: x.left.parent = p
        x.left = p
    p.parent = x
    x.parent = g
    if g:
        if g.left is p: g.left = x
        else: g.right = x

def splay(x):
    while x.parent:
        p = x.parent
        g = p.parent
        if g:
            rotate(p if (g.left is p) == (p.left is x) else x)
        rotate(x)
    return x

def merge(a, b):
    if a is None: return b
    if b is None: return a
    x = a
    while x.right:
        x = x.right
    splay(x)
    x.right = b
    b.parent = x
    return x

def reroot(v):
    splay(v)
    L = v.left
    if L:
        L.parent = None
        v.left = None
    return merge(v, L)

def connected(u, v):
    splay(u)
    cur = v
    while cur.parent is not None:
        cur = cur.parent
    return cur is u

def link(u, v, tok):
    u_root = reroot(u)
    v_root = reroot(v)
    e1 = Node(('e', tok, 0))
    e2 = Node(('e', tok, 1))
    t = merge(u_root, e1)
    t = merge(t, v_root)
    t = merge(t, e2)
    return e1, e2

def cut(e1, e2):
    splay(e1)
    cur = e2
    while cur.parent is not e1:
        cur = cur.parent
    if cur is e1.left:
        e_before, e_after = e2, e1
    else:
        e_before, e_after = e1, e2
    splay(e_before)
    A, Rest = e_before.left, e_before.right
    if A: A.parent = None
    if Rest: Rest.parent = None
    splay(e_after)
    M, C = e_after.left, e_after.right
    if M: M.parent = None
    if C: C.parent = None
    merge(A, C)
    return M

def solve():
    data = sys.stdin.read().split()
    idx = 0
    n = int(data[idx]); idx += 1
    q = int(data[idx]); idx += 1
    vnode = [Node(('v', i)) for i in range(n)]
    edge_tok = {}
    out = []
    for _ in range(q):
        typ = data[idx]; idx += 1
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        if typ == '1':
            e1, e2 = link(vnode[u], vnode[v], (u, v))
            edge_tok[(u, v)] = (e1, e2)
            edge_tok[(v, u)] = (e1, e2)
        elif typ == '2':
            e1, e2 = edge_tok.pop((u, v))
            edge_tok.pop((v, u), None)
            cut(e1, e2)
        else:
            out.append("Yes" if connected(vnode[u], vnode[v]) else "No")
    print('\n'.join(out))

solve()

計算量: Splay木ベースのため各操作 amortized $O(\log N)$。全体 $O((N+Q)\log N)$。

Step-by-Step 解説

Step 1: Euler ツアーを列として表現

頂点・辺トークンをノードオブジェクトとして直接保持することで、「頂点 $v$ の位置」を $O(1)$ でノード参照から取得できる。

Step 2: reroot（根の付け替え）

$v$ を splay して根にし、左部分木を切り離して merge(v以降, 前半) とすることで列を回転させる。

Step 3: link と cut

link は reroot 後に「$u$の列 → 辺トークン → $v$の列 → 辺トークン」の順に連結。cut は先に現れる辺トークンを splay して右部分木を切り離し、もう一方でさらに分割する。

Step 4: connected

$u$ を splay して根にし、$v$ から親をたどって到達するノードが $u$ 自身かどうかで判定する。

よくあるミス

次のステップ

• 発展問題: 部分木の総和・最小値など集約情報を載せる
• 比較学習: Link-Cut Tree との使い分け（LCT はパス、ETT は部分木・連結性）

自己評価