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

2026-08-20 赤色 Master / Phase 8+ ★★★★★★★★★ DFS+Union-Findで複数LCAクエリを一括処理しO((N+Q)α(N))で解く

問題

$N$頂点の木（頂点1を根）が与えられる。$Q$個のクエリ$(u_i,v_i)$それぞれについて最小共通祖先（LCA）を求めよ。

入力形式

N
u_1 v_1
...
u_{N-1} v_{N-1}
Q
u_1 v_1
...
u_Q v_Q

制約

$2 \le N \le 200000$
$1 \le Q \le 200000$
与えられる辺は木を成す
$u_i=v_i$の場合、答えは$u_i$自身

入出力例

入力例1

5
1 2
1 3
2 4
2 5
3
4 5
4 3
2 5

出力例1

2
1
2

木は1が根、子2と3、2の子が4と5。(4,5)→2、(4,3)→1、(2,5)→2。

概念図

入力例1の木構造 1 2 3 4 5 LCA(4,5)=2（青）／LCA(4,3)=1（黄）／LCA(2,5)=2

ヒント（段階的開示）

ヒント1（方向性）

ダブリングLCA（二分累乗で$2^k$上の祖先テーブルを構築し各クエリ$O(\log N)$）は既習。今回は全クエリを先に受け取れる条件を活かし、木を1回だけDFSしながらUnion-Findで祖先情報を管理するTarjanのオフラインアルゴリズムで解く。

ヒント2（アプローチ）

頂点を白（未訪問）→灰（探索中）→黒（部分木完了）の3状態で管理。ある頂点$u$を黒に塗る瞬間に$u$のクエリ$(u,v)$を確認、$v$が既に黒ならUnion-Findの代表元に対応する$ancestor$がLCA。子の探索完了ごとに親へunionし、$ancestor$を親自身に更新する。

ヒント3（誘導） 
def tarjan_lca(u, parent):
    make_set(u); ancestor[find(u)] = u
    for v in children(u):
        tarjan_lca(v, u)
        union(u, v)
        ancestor[find(u)] = u
    color[u] = BLACK
    for (v, query_id) in queries[u]:
        if color[v] == BLACK:
            answer[query_id] = ancestor[find(v)]

Nが大きいため実装では明示スタックによる反復DFSに書き換える。

模範解答 (Python)

import sys


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

    adj = [[] for _ in range(n + 1)]
    for _ in range(n - 1):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        adj[u].append(v)
        adj[v].append(u)

    q = int(data[idx]); idx += 1
    query_list = [[] for _ in range(n + 1)]
    for i in range(q):
        u = int(data[idx]); idx += 1
        v = int(data[idx]); idx += 1
        query_list[u].append((v, i))
        query_list[v].append((u, i))

    parent = list(range(n + 1))

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

    ancestor = list(range(n + 1))
    color = [0] * (n + 1)  # 0=白, 1=灰, 2=黒
    ans = [0] * q

    root_node = 1
    color[root_node] = 1
    ancestor[find(root_node)] = root_node
    stack = [(root_node, 0, iter(adj[root_node]))]

    while stack:
        node, par, it = stack[-1]
        pushed_child = None
        for nxt in it:
            if nxt == par:
                continue
            if color[nxt] == 0:
                pushed_child = nxt
                break

        if pushed_child is not None:
            color[pushed_child] = 1
            ancestor[find(pushed_child)] = pushed_child
            stack.append((pushed_child, node, iter(adj[pushed_child])))
            continue

        for (other, qi) in query_list[node]:
            if color[other] == 2:
                ans[qi] = ancestor[find(other)]
        color[node] = 2
        stack.pop()

        if stack:
            parent_node = stack[-1][0]
            root_a = find(node)
            root_b = find(parent_node)
            parent[root_a] = root_b
            ancestor[find(parent_node)] = parent_node

    print('\n'.join(str(a) for a in ans))


solve()

Step-by-Step 解説

1DFSの色分けと反復化
明示スタック[(node, parent, iterator)]で「探索中＝灰」「戻ってきた＝黒」を表現する。未訪問の子が見つかれば掘り下げ、なければそのノードを完了させる。
2Union-Findとancestor配列
ancestor[root]は「その集合が表す部分木の、現時点でDFSが見えている最も浅い頂点」。子の探索完了後に親へunionしancestor[find(親)]=親と更新する。
3クエリの解決タイミング
頂点uを黒に塗る直前にuのクエリ(u,v)を確認。vが既に黒ならその集合のancestorがLCA。逆側のクエリ登録により後で解決される場合もある。
4findによるパス圧縮
経路圧縮（path halving）により、Union-Find全体で償却$O(\alpha(N))$（実質定数）に抑えられる。
5計算量
DFS$O(N)$、クエリ走査$O(Q)$、Union-Find操作$O((N+Q)\alpha(N))$。全体で$O((N+Q)\alpha(N))$。

よくあるミス

ミス原因正しい書き方
クエリを片方の頂点にしか登録しない対称性の見落としquery_list[u]とquery_list[v]の両方に登録する
unionの方向を逆にしてancestorの更新先を間違える親子の付け替え方向の混同子の根を親の根に付け替え、ancestor[find(親)]を更新する
再帰DFSのままNが大きいケースで実行しスタックオーバーフローするPythonの再帰上限超過明示スタックによる反復DFSに書き換える
黒判定を訪問済み（灰含む）で行ってしまう色を2値管理してしまう白・灰・黒の3値管理にし黒のみを判定条件にする

次のステップ

  • 発展: LCAが求まれば2頂点間の距離やパス上のクエリにも応用できる。頻繁な追加クエリにはダブリングLCAとの使い分けを検討する
  • 次回予告: 下限付き最大流（Lower Bound Flow）

自己評価

自分の回答

気づき・メモ