hihoCoder #1067：最近公共祖先·二——Tarjan 離線演算法詳解

問題描述

給定 N 對父子關係（構成一棵樹），所有人共享一個公共祖先（根節點）。需回答 M 個查詢：任意兩人的所有共同祖先中，輩分最低（即最近）的是誰？

數據範圍：N, M ≤ 10^5，需高效演算法。

Tarjan 離線 LCA 演算法原理

Tarjan 演算法結合 深度優先搜索 (DFS) 與 並查集，在一次遍歷中解決所有查詢，時間複雜度 O(N + M)。

核心定理

若節點 u、v 分別位於節點 t 的不同子樹中，則 t 為 u、v 的最近公共祖先。若一節點是另一節點的祖先，則該祖先節點即為 LCA。

演算法流程

1. 從根節點開始 DFS。
2. 訪問節點 u 時，初始化並查集：father[u] = u，標記 ancestor[u] = u。
3. 遞歸訪問 u 的每個子樹 v，完成後將 v 合併到 u：Union(u, v)，並更新 ancestor[Find(u)] = u。
4. 處理與 u 相關的所有查詢 (u, x)：若 x 已被訪問，則 LCA(u, x) = ancestor[Find(x)]。
5. 標記 u 為已訪問。

圖解演示

以樹結構為例，分步驟展示並查集合併過程與祖先標記更新：

遍歷順序：1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 ... 每完成一個子樹合併，該子樹內任意兩節點的 LCA 即為當前根。

關鍵代碼框架 (C++)

const int MAXN = 1e5 + 5;
vector<int> tree[MAXN];
vector<pair<int, int>> query[MAXN]; // {對方節點, 查詢編號}
int ancestor[MAXN], father[MAXN], ans[MAXN];
bool visited[MAXN];

int Find(int x) { return x == father[x] ? x : father[x] = Find(father[x]); }

void Union(int x, int y) { father[Find(x)] = Find(y); }

void Tarjan(int u) {
    ancestor[u] = father[u] = u;
    for (int v : tree[u]) {
        Tarjan(v);
        Union(u, v);
        ancestor[Find(u)] = u;
    }
    visited[u] = true;
    for (auto [v, idx] : query[u]) {
        if (visited[v]) ans[idx] = ancestor[Find(v)];
    }
}

複雜度與優勢

• 時間：O((N + M) α(N))，近乎線性。
• 空間：O(N + M)。
• 離線特性：需預讀所有查詢，適合批量處理場景。