← 返回首頁

Tarjan Offline LCA 離線最近公共祖先

選擇樹：

新增查詢：LCA( , )

未訪問

進行中 (in-stack)

已完成

當前節點

查詢列表：

樹結構 & DFS 遍歷

查詢結果

Tarjan 離線 vs Binary Lifting 線上比較

	Tarjan 離線 LCA	Binary Lifting
預處理	O(n)	O(n log n)
單次查詢	N/A (批次處理)	O(log n)
q 次查詢	O(n + q)	O(n log n + q log n)
適用場景	離線 (查詢事先已知)	線上 (即時查詢)
核心技術	DFS + Union-Find	倍增法 + 稀疏表

演算法說明

Tarjan 離線 LCA 利用 DFS + Union-Find 一次遍歷回答所有 LCA 查詢。

DFS 遍歷樹，每個節點離開時合併到父節點
若查詢 (u, v) 中 v 已被訪問，則 LCA(u, v) = ancestor[find(v)]
時間複雜度：O((n + q) * alpha(n))，近似 O(n + q)
適合查詢數量大且可離線處理的場景