Tarjan 離線 LCA：一次 DFS 回答所有 LCA 查詢

Binary Lifting 隨時能回答；Tarjan 是「先把問題全收起來，一次 DFS 全部解決」的批量策略。

線上 vs 離線

線上（Binary Lifting）：O(n log n) 預處理，每次查詢 O(log n)。查詢可以即時回答，適合互動式場景。

離線（Tarjan）：先收集所有查詢，一次 DFS 批量回答，O((n + q) α(n)) ≈ O(n + q)。若 q 很大且可以批量處理，比 Binary Lifting 快。

核心思想

DFS 遍歷樹，離開節點時把它合併到父節點的 Union-Find 集合：

當 DFS 到達節點 u：
  初始化 u 的集合（find(u) = u）

遞迴所有子節點 v 後，把 v 合併到 u：
  union(v → u)，讓 find(v) = u

標記 u 已訪問

對所有查詢 (u, v) 中「v 已訪問」的情況：
  LCA(u, v) = find(v)

為什麼 find(v) = LCA(u, v)？

當 DFS 到達 u，v 已被訪問且已回溯：
  v 在 LCA(u,v) 的某個子樹中
  v 回溯後，find(v) 已被更新為 v 的集合代表
  = v 到根路徑上、且 DFS 已完全回溯的最近節點
  = LCA(u, v)

實作

int[] parent = new int[n];
boolean[] visited = new boolean[n];
int[] answer = new int[q];
 
// Union-Find
int find(int x) { return parent[x] == x ? x : (parent[x] = find(parent[x])); }
void union(int x, int y) { parent[find(x)] = find(y); }
 
void dfs(int u, int par) {
    parent[u] = u; // find(u) = u
 
    for (int v : adj[u]) {
        if (v == par) continue;
        dfs(v, u);
        union(v, u); // 把 v 的集合合併到 u（代表節點設為 u）
    }
 
    visited[u] = true;
 
    for (Query q : queries[u]) { // 所有涉及 u 的查詢
        if (visited[q.other]) {
            answer[q.idx] = find(q.other);
        }
    }
}

完整流程

1. 建查詢鄰接表：queries[u] 存所有涉及 u 的查詢（包含對端節點和查詢編號）
2. 從根 DFS
3. DFS 結束後，所有查詢都有答案

何時選 Tarjan vs Binary Lifting？

	Tarjan	Binary Lifting
預處理	O(n + q)	O(n log n)
單次查詢	批量，無法即時	O(log n)
路徑最大值	需要額外維護	容易擴展
適合	q 大且可離線	即時查詢

若 q 遠大於 n，Tarjan 更快；若需要擴展（路徑最大值、第 k 個祖先），Binary Lifting 更靈活。

---

Tarjan LCA 的巧妙是：DFS 的回溯順序恰好和 LCA 的「公共祖先」關係吻合——DFS 回溯 = 自然地找到了公共祖先。