HDU 2586 最近公共祖先離線算法：Tarjan + 並查集詳解

問題描述

給定一棵 N (≤40,000) 節點的有根樹（邊有權），M 個查詢 (u,v)，求每對節點的最近公共祖先（LCA）距離。多測試用例。

Tarjan 離線 LCA 核心思想

利用 DFS 遍歷樹，配合並查集維護已訪問節點的祖先關係。關鍵性質：當 DFS 回溯到節點 u 時，u 的子樹已完全訪問，此時 u 就是當前並查集中 u 所在集合的代表元（ancestor）。對於查詢 (u,v)，若 v 已訪問，則 LCA(u,v) = ancestor[find(v)]。

算法流程

1. 建樹、讀查詢（雙向存入 Qes[u]）。
2. vst[1]=1; LCA(1); 從根 DFS。
3. DFS 中：
   • 遞歸訪問子節點 v，累加距離 dist[v] = dist[u] + w。
   • 回溯時 f[v] = u（合併並查集，代表元設為父節點）。
   • 處理 u 的所有查詢：若對端 v 已訪問（vst[v]），則 ans[id] = dist[u] + dist[v] - 2*dist[ find(v) ]。

核心代碼

struct Edge { int to, cost; };
vector<Edge> tree[MAXN], Qes[MAXN];
int f[MAXN], dist[MAXN], ancestor[MAXN], ans[MAXN];
bool vst[MAXN];

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

void LCA(int u) {
    for (auto &e : tree[u]) {
        if (!vst[e.to]) {
            vst[e.to] = 1;
            dist[e.to] = dist[u] + e.cost;
            LCA(e.to);
            f[e.to] = u;                 // 並查集合併：子樹代表元指向父
            // 處理 e.to 相關的查詢
            for (auto &qe : Qes[e.to]) {
                if (vst[qe.to] && ans[qe.cost] == -1) {
                    int lca = Find(qe.to);
                    if (qe.to == e.to) ans[qe.cost] = 0;
                    else ans[qe.cost] = dist[e.to] + dist[qe.to] - 2*dist[lca];
                }
            }
        }
    }
}

複雜度分析

• 時間：O((N+M) α(N))，近似線性，極快。
• 空間：O(N+M)。

關鍵細節

• 查詢雙向存儲：Qes[u].push({v,id}); Qes[v].push({u,id});，確保無論先訪問誰都能處理。
• ans[] 初始化為 -1，防止重複計算。
• 距離公式：dist[u] + dist[v] - 2*dist[lca]，利用根到各點距離。
• 並查集路徑壓縮 Find 必須寫遞歸或迭代壓縮，保證近乎 O(1)。

為什麼離線比線上快？

線上 LCA（倍增/ST 表/線段樹）預處理 O(N log N)，查詢 O(log N) 或 O(1)。但本題 N=40,000, M 未給上限（可能很大），離線 Tarjan 總複雜度 O(N+M)，無 log 因子，實測更快且代碼簡短。