Day 048-Q1 — Offline LCT（辺削除の分割統治 + Undo DSU）

2026-06-01 赤色 Master / Phase 8+ ★★★★★★★★★ Offline Dynamic Connectivity / Segment Tree on Time Axis

問題

$N$ 頂点のグラフに対して、$Q$ 個のクエリが与えられる。各クエリは以下のいずれか：

  • add i: 辺 $e_i$ をグラフに追加する
  • remove i: 辺 $e_i$ をグラフから削除する（必ず以前に追加済み）
  • query u v: 頂点 $u$ と頂点 $v$ が連結かどうか答える

辺の存在期間（追加〜削除）を時刻軸の区間として管理し、各 query クエリに O(log Q) で答えよ。

制約

$2 \le N \le 3 \times 10^4$
$1 \le M \le 10^5$（辺の総種類数）
$1 \le Q \le 10^5$（クエリ総数）
自己ループ・多重辺なし
時間制限: 3秒

入出力例

入力例 1

5 3 7
1 2
2 3
3 4
add 0
add 1
query 1 3
remove 0
add 2
query 1 4
query 2 4

出力例 1

Yes
Yes
No

概念図: 時刻軸セグメント木と辺の配置

時刻軸 (Q=8クエリ) t=0 t=1 t=2 t=3 t=4 t=5 t=6 t=7 辺0: t=[0,2] 辺1: t=[1,7]（削除なし → 末尾まで） 辺2: t=[4,7] 時刻軸セグメント木（各辺をO(log Q)ノードに分配） root [0,7] [0,3] [4,7] ← 辺2 DFS: 各ノードで辺をUnion → リーフでqueryに回答 → 戻りがけにUndo

ヒント（段階的開示）

ヒント1: 方向性
「辺の存在期間」を時刻軸上の区間として捉えましょう。各辺が存在する時刻区間 $[l, r)$ を、時刻軸上のセグメント木の対応ノードに登録します。これがオフライン動的連結性の核心です。
ヒント2: アプローチ
  • 時刻軸セグメント木（サイズ Q）を構築し、辺の存在区間を O(log Q) ノードに分配
  • セグメント木を再帰的にDFSし、各ノードで辺を Union-Find でマージ
  • リーフ（各クエリ時刻）で query 操作に回答
  • DFS の戻りがけに Union を Undo（ランクベース Union のみ使用）
  • Path compression は Undo 不可能なので禁止
ヒント3: Undo DSU の実装骨格 
class UndoDSU:
    def __init__(self, n):
        self.parent = list(range(n+1))
        self.rank = [0] * (n+1)
        self.history = []

    def find(self, x):  # path compression 禁止
        while self.parent[x] != x:
            x = self.parent[x]
        return x

    def union(self, u, v):
        u, v = self.find(u), self.find(v)
        if u == v:
            self.history.append(None)
            return
        if self.rank[u] < self.rank[v]:
            u, v = v, u
        self.history.append((u, self.rank[u], v, self.parent[v]))
        self.parent[v] = u
        if self.rank[u] == self.rank[v]:
            self.rank[u] += 1

    def undo(self):
        op = self.history.pop()
        if op is None: return
        u, ru, v, pv = op
        self.parent[v] = pv
        self.rank[u] = ru

模範解答 (Python)

import sys
from sys import stdin

def solve():
    data = stdin.read().split()
    idx = 0
    N, M, Q = int(data[idx]), int(data[idx+1]), int(data[idx+2]); idx += 3
    edges = []
    for _ in range(M):
        u, v = int(data[idx]), int(data[idx+1]); idx += 2
        edges.append((u, v))

    queries = []
    for _ in range(Q):
        line = []
        line.append(data[idx]); idx += 1
        if line[0] in ('add', 'remove'):
            line.append(int(data[idx])); idx += 1
        else:
            line.append(int(data[idx])); idx += 1
            line.append(int(data[idx])); idx += 1
        queries.append(line)

    seg_edges = [[] for _ in range(4 * Q + 4)]

    def seg_add(node, l, r, ql, qr, edge_id):
        if ql > r or qr < l or ql > qr:
            return
        if ql <= l and r <= qr:
            seg_edges[node].append(edge_id)
            return
        mid = (l + r) >> 1
        seg_add(2*node, l, mid, ql, qr, edge_id)
        seg_add(2*node+1, mid+1, r, ql, qr, edge_id)

    edge_start = {}
    query_ptr = {}
    time = 0
    for q in queries:
        if q[0] == 'add':
            edge_start[q[1]] = time
        elif q[0] == 'remove':
            eid = q[1]
            start = edge_start.pop(eid)
            seg_add(1, 0, Q-1, start, time-1, eid)
        else:
            query_ptr[time] = (q[1], q[2])
        time += 1

    for eid, start in edge_start.items():
        seg_add(1, 0, Q-1, start, Q-1, eid)

    class UndoDSU:
        def __init__(self, n):
            self.parent = list(range(n+1))
            self.rank = [0] * (n+1)
            self.history = []

        def find(self, x):
            while self.parent[x] != x:
                x = self.parent[x]
            return x

        def union(self, u, v):
            u, v = self.find(u), self.find(v)
            if u == v:
                self.history.append(None)
                return
            if self.rank[u] < self.rank[v]:
                u, v = v, u
            self.history.append((u, self.rank[u], v, self.parent[v]))
            self.parent[v] = u
            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

        def undo(self):
            op = self.history.pop()
            if op is None: return
            u, ru, v, pv = op
            self.parent[v] = pv
            self.rank[u] = ru

        def connected(self, u, v):
            return self.find(u) == self.find(v)

    dsu = UndoDSU(N)
    answers = {}

    def dfs(node, l, r):
        cnt = len(seg_edges[node])
        for eid in seg_edges[node]:
            u, v = edges[eid]
            dsu.union(u, v)
        if l == r:
            if l in query_ptr:
                u, v = query_ptr[l]
                answers[l] = 'Yes' if dsu.connected(u, v) else 'No'
        else:
            mid = (l + r) >> 1
            dfs(2*node, l, mid)
            dfs(2*node+1, mid+1, r)
        for _ in range(cnt):
            dsu.undo()

    if Q > 0:
        sys.setrecursionlimit(300000)
        dfs(1, 0, Q-1)

    for t, _, _ in [(t, u, v) for t, (u, v) in sorted(query_ptr.items())]:
        print(answers.get(t, 'No'))

solve()

Step-by-Step 解説

1辺の存在区間の計算
各辺の add 時刻を記録し、remove 時刻が来たら区間 [add_time, remove_time - 1] を確定。削除されなかった辺は [add_time, Q-1]。
2セグメント木への辺の分配
時刻軸セグメント木の区間更新と同様に、各辺の存在区間を O(log Q) 個のノードに分配する。各ノードに辺リストを持たせる。
3DFS + Union
セグメント木をDFSし、各ノードで対応する辺を Union。リーフで query に回答。
4Undo によるロールバック
DFS の戻りがけに Union 操作を Undo（スタックから取り出してロールバック）。ランクベース Union のみ使用し、路径圧縮は禁止。
5計算量の確認
各辺は O(log Q) ノードに分配。各ノードでの Union/Undo は O(log N)。全体 $O((M + Q) \log Q \cdot \log N)$。

計算量

前処理（辺の区間分配）: $O(M \log Q)$
DFS（Union + Undo）: $O((M + Q) \log Q \cdot \log N)$
全体: $O((M + Q) \log Q \log N)$
空間: $O(N + (M + Q) \log Q)$

よくあるミス

ミス原因正しい書き方
path compression を使うUndo が不可能になるランクベース Union のみ使用
残存辺を登録し忘れる削除されなかった辺が無視されるループ後に残存辺を [start, Q-1] で登録
undo の回数がずれるNone をスタックに積み忘れ同一成分の union でも history に None を push
再帰上限に達するQ=10^5 でセグメント木深さ約17sys.setrecursionlimit を十分大きく設定

次のステップ

  • 発展問題: Link-Cut Tree を使ったオンライン動的連結性（辺追加・削除・連結判定をオンラインで O(log N)）
  • 関連: Day029 Q1（Offline LCT の辺削除版）の復習
  • 応用: 動的グラフのコンポーネント数維持、時刻付きクエリ処理

自己評価