Day 110-Q2 | Euler Tour Tree

問題

$N$頂点の森（最初は辺なし）に対して $Q$ 個のクエリをオンラインで処理する。

1 u v：辺 $(u,v)$ を追加（追加前は非連結が保証される）
2 u v：辺 $(u,v)$ を削除（存在が保証される）
3 u v：$u,v$ が連結か判定し Yes/No を出力

入力形式

N Q
query_1
...
query_Q

制約

$1 \le N,Q \le 2000$

$1 \le u,v \le N,\ u\neq v$

各クエリの前提は常に満たされる

入出力例

入力例1

出力例1

Yes
No

辺(1,2),(2,3)追加後は1,3が連結→Yes。辺(2,3)削除後は非連結→No。

概念図: re-root（根の付け替え）とオイラーツアー

ヒント（段階的開示）

ヒント1: 方向性

Union-Findは併合と判定は高速だが、一度併合した集合を分離できない。辺の削除に対応する動的な森の管理構造が必要になる。

ヒント2: アプローチ

Euler Tour Tree (ETT) は木を根からのDFS訪問列（オイラーツアー、長さ $2n-1$）として管理する。同じ列に属していれば連結。link/cutは列の re-root（回転）・分割・連結として実現する。本来は平衡二分木で $O(\log n)$、本問の制約では簡略化した隣接集合+BFSでも十分高速。

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

from collections import deque
adj = [set() for _ in range(n + 1)]
def connected(u, v):
    if u == v:
        return True
    visited = {u}
    q = deque([u])
    while q:
        cur = q.popleft()
        for nxt in adj[cur]:
            if nxt == v:
                return True
            if nxt not in visited:
                visited.add(nxt); q.append(nxt)
    return False

模範解答 (Python)

import sys
from collections import deque

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

    adj = [set() for _ in range(n + 1)]
    out = []

    def connected(u, v):
        if u == v:
            return True
        visited = [False] * (n + 1)
        visited[u] = True
        dq = deque([u])
        while dq:
            cur = dq.popleft()
            for nxt in adj[cur]:
                if nxt == v:
                    return True
                if not visited[nxt]:
                    visited[nxt] = True
                    dq.append(nxt)
        return False

    for _ in range(q):
        t = int(data[idx]); idx += 1
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        if t == 1:
            adj[u].add(v)
            adj[v].add(u)
        elif t == 2:
            adj[u].discard(v)
            adj[v].discard(u)
        else:
            out.append("Yes" if connected(u, v) else "No")

    print("\n".join(out))

solve()

計算量: 隣接集合+BFSの簡略実装で $O(Q \times N)$（$N,Q\le2000$なら余裕）。真のETT（平衡二分木）ならlink/cut/connectedすべて $O(\log n)$ 償却。入力例1で出力 Yes / No が一致することを確認済み。

Step-by-Step 解説

1なぜUnion-Findでは不十分か
Union-Findは分離（cut相当）に対応できない。

2オイラーツアーで木を列として表現する
根からのDFS訪問列（長さ$2n-1$）に翻訳する。同じ列＝連結。

3re-rootで列を回転する
頂点を新しい根にする操作を、列中でその頂点が最初に現れる位置での分割・入れ替えとして実現する。

4linkは列の連結、cutは列の分割
本問では隣接集合の更新+BFSに置き換えている。

5簡略実装と本来のETTの対応関係を意識する
考え方は同じで、データ構造の実装コストだけが異なる。

よくあるミス

ミス	原因	正しい書き方
linkクエリで既連結を疑い余計な事前チェックをする	前提「非連結」を信頼しない	前提を信頼し素直に辺を追加/削除する
存在しない辺の削除が無言で成功したように見える	`set.discard`は例外を出さない	デバッグ時は`remove`で例外検証する
BFSの`visited`を使い回す	クエリごとの初期化漏れ	クエリごとに新規`visited`を用意する
簡略実装の計算量をそのまま大規模な制約に適用しTLEする	学習用実装と本番実装の計算量差を混同	$N,Q$が大きい場合は平衡二分木ベースの本実装が必須

次のステップ

発展: Treapでオイラーツアー列を管理し真の$O(\log n)$を実装する
発展: 部分木の集約値（サイズ・総和）を持つ「重み付きETT」に発展させる
発展: Link-Cut Treeとの使い分け（ETTはconnected向き、LCTはパスクエリ向き）を整理する

自己評価

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

Day 110-Q2 — Euler Tour Tree（オンライン森の連結性維持）

問題