HDU 2586 How Far Away?：Tarjan 離線 LCA 求樹上兩點距離

題目與模型

給定 n ≤ 4×10⁴ 節點的樹（邊帶權），m ≤ 4×10⁴ 次詢問 (u, v)，求兩點間路徑長度（邊權和）。多測資。

離線 Tarjan LCA 核心流程

1. 建圖：鄰接表存樹邊；查詢雙向存入 query[u]，並記錄查詢編號 qid[u]。
2. DFS 遍歷：從根（1）出發，維護 dist[u] = 根到 u 距離，pnt[u] = 并查集父節點，vis[u] = 已訪問。
3. 回溯時合併：訪問完子樹 v，pnt[v] = u（并查集 union）。
4. 處理查詢：在 u 訪問完所有子樹後，遍歷 query[u]，若對端 v 已 vis[v]，則 LCA = find(v)，答案 dist[u] + dist[v] - 2*dist[LCA]。

關鍵代碼片段

void dfs(int u, int d) {
    dist[u] = d; vis[u] = 1; pnt[u] = u;
    for (v in children) if (!vis[v]) {
        dfs(v, d + w);
        pnt[v] = u; // union
    }
    for (each query (u, v, id)) if (vis[v]) {
        ans[id] = dist[u] + dist[v] - 2 * dist[find(v)];
    }
}

棧溢出問題與解決

HDU Windows 判題機棧極小，深度 4×10⁴ 遞迴會爆棧。解決方案：

• G++ 編譯時加 #pragma comment(linker, "/STACK:1024000000,1024000000") 擴大棧至 1GB。
• 或改寫非遞迴 DFS（手動棧），但較繁瑣。

複雜度

• 時間 O((n+m) α(n))，近似線性。
• 空間 O(n+m)。

總結

本題是「樹上路徑查詢」的離線經典解法。Tarjan LCA 利用 DFS 後序 + 并查集動態維護祖先關係，將多次 LCA 查詢攤平成近似常數時間。實作時需注意：并查集 union 方向固定為子→父，且查詢處理必須在子樹全部回溯後，保證 LCA 已正確合併。HDU 特有的棧限制需用編譯指令繞過。