Day 016-Q2 | オフラインLCA (Tarjan)

問題

$N$ 頂点の根付き木（根 = 1）と、$Q$ 個のクエリ $(u_i, v_i)$ が与えられる。

各クエリについて $\text{LCA}(u_i, v_i)$（最小共通祖先）を求めよ。

ただし、Tarjan のオフライン LCA アルゴリズム（Union-Find を用いる方法）で実装すること。オンライン LCA（Euler Tour + Sparse Table 等）は不可。

入力形式

N Q
u_1 v_1
u_2 v_2
（N-1 本の辺）
（各クエリ）

制約

$2 \le N \le 5 \times 10^5$

$1 \le Q \le 5 \times 10^5$

木は連結

（入力形式: 木の辺 N-1 本を先に読み、次に Q クエリを読む）

入出力例

入力例 1

出力例 1

1
1
1

（LCA(4,6)=1, LCA(5,7)=1, LCA(2,3)=1）

ヒント (段階的開示)

ヒント1: 方向性

Tarjan の LCA は DFS 中に Union-Find を利用。各頂点を訪問し終えた（バックトラック後）ときに Union-Find で祖先を記録する。

ヒント2: アプローチ

ancestor[v] = v のグループの代表（現在の LCA 候補）
頂点 v のすべての子を再帰処理後、v を親にマージ
クエリ (u, v) は: u が処理済みなら ancestor[find(u)] が答え

ヒント3: 誘導

def dfs(v, par):
    ancestor[v] = v  # 自分が代表
    for child in tree[v]:
        if child == par: continue
        dfs(child, v)
        union(v, child)   # child のグループを v に統合
        ancestor[find(v)] = v  # 代表の祖先を v に更新
    visited[v] = True
    for (u, idx) in queries[v]:  # v を含むクエリ
        if visited[u]:
            ans[idx] = ancestor[find(u)]

模範解答 (Python)

import sys
from collections import defaultdict
sys.setrecursionlimit(600000)
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    tree = defaultdict(list)
    for _ in range(N - 1):
        u, v = map(int, input().split())
        tree[u].append(v)
        tree[v].append(u)

    queries_at = defaultdict(list)  # queries_at[v] = [(u, idx)]
    for i in range(Q):
        u, v = map(int, input().split())
        queries_at[u].append((v, i))
        queries_at[v].append((u, i))

    # Union-Find
    parent = list(range(N + 1))
    rank = [0] * (N + 1)

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]  # path compression
            x = parent[x]
        return x

    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry: return
        if rank[rx] < rank[ry]:
            rx, ry = ry, rx
        parent[ry] = rx
        if rank[rx] == rank[ry]:
            rank[rx] += 1

    ancestor = list(range(N + 1))
    visited = [False] * (N + 1)
    ans = [0] * Q

    # 再帰をスタックで実装（N が大きいため）
    # フェーズ: 0=子を処理前, 1=処理後のマージフェーズ
    stack = [(1, 0, False)]  # (node, parent, phase)
    child_iter = [iter([])] * (N + 1)
    for v in range(1, N + 1):
        child_iter[v] = iter(tree[v])

    # 反復DFSでは実装が複雑なので、sys.setrecursionlimit を上げて再帰で実装
    def dfs(v, par):
        ancestor[v] = v
        for u in tree[v]:
            if u == par:
                continue
            dfs(u, v)
            union(v, u)
            ancestor[find(v)] = v
        visited[v] = True
        for (u, idx) in queries_at[v]:
            if visited[u]:
                ans[idx] = ancestor[find(u)]

    dfs(1, -1)
    print('\n'.join(map(str, ans)))

main()

Step-by-Step 解説

1Tarjan LCA のコアアイデア
DFS の「帰りがけ」に Union-Find を更新。v を処理し終えたとき、v のグループの代表を v の祖先として記録。

2クエリの処理タイミング
クエリ $(u, v)$ の答えが確定するのは：「$u$ が処理済み（visited[u]=True）かつ $v$ が現在スタック上にある（= バックトラック中）」のとき。このとき ancestor[find(u)] が LCA。

3Union-Find の経路圧縮
ancestor[find(v)] = v で「グループの代表はその部分木を含む最浅の訪問済み頂点」を維持する。

4計算量

DFS: $O(N)$
Union-Find（経路圧縮 + rank）: $O(\alpha(N))$ amortized
全体: $O((N + Q) \alpha(N))$

オンライン LCA（$O(N \log N)$ 前処理 + $O(\log N)$ クエリ）に比べ、オフラインでより単純な実装で高速。

よくあるミス

ミス	原因	正しい書き方
`ancestor[find(v)] = v` を忘れる	union 後の代表更新漏れ	union と ancestor 更新はセット
クエリを片方向だけ登録	`queries_at[u]` だけに追加	`queries_at[u]` と `queries_at[v]` 両方に追加
再帰深さ超過	N=5×10^5 でデフォルト制限	`sys.setrecursionlimit(600000)`

次のステップ

発展問題: オフライン LCA を利用した「根付き木上の任意2点間の辺重みの最大値・最小値クエリ」($Q$ 個のオフラインクエリを $O((N+Q)\alpha(N))$ で処理)

自己評価

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

Day 016-Q2 — オフラインLCA（Tarjanのアルゴリズム）

問題