累計跳躍次數（jumps）：0
紅色為當前跳躍指標；黃框為 u、v 兩指標；綠色（粗框）為已確定的 LCA；綠色粗邊為查詢路徑上的邊；節點上方數字為深度。
想像一張家族族譜:兩個表兄弟各自往上追爸爸、爺爺,追到某一代第一次「碰頭」的那位長輩,就是他們最近的共同祖先。樹狀結構也常要問這種問題——兩個節點分岔之前,最後一起經過的那個點是誰?算出來能拿來量樹上兩點的距離、或判斷誰是誰的後代,是很多樹上演算法的基本零件。這頁把同一棵樹交給兩種找法比一比:一種每問一次就當場回答,一種先把問題全收齊、再一口氣解完。下面你會看到它們在同一組查詢上各自怎麼跑。
樹上兩節點 u、v 的最近共同祖先（LCA）是同時為 u、v 祖先、且深度最大的節點。這裡用同一棵樹對比兩種經典解法： Binary Lifting（倍增法）屬於線上（online）解法，預處理 O(n log n) 建稀疏表後，每次查詢只需 O(log n)、可即時回答任意 (u, v)； Tarjan 離線 LCA屬於離線（offline）解法，查詢集合須事先給定，一次 DFS 搭配並查集即可 O(n+q) 批次回答全部查詢，但不能中途插入新查詢。
先用 BFS 求每個節點的 depth 與直接父節點 up[v][0]，再遞推建稀疏表 up[v][j] = up[ up[v][j-1] ][j-1]（跳 2^j 步 = 兩次跳 2^(j-1) 步）。 查詢時先把較深的節點依深度差二進制上跳到同深度，若相等即為 LCA；否則兩指標一起從大到小二進制上跳，直到跳到 LCA 正下方，回傳其共同父節點。
DFS 進入節點 u 時設 ancestor[u]=u；遞迴走訪每個非父子節點 v 後回溯，將 v 所在集合併入 u（union），並設 ancestor[find(u)]=u； 標記 u 已訪問後，檢查所有掛在 u 上的查詢 (u, w)：若對端 w 已訪問，代表兩者已在同一 DFS 子樹外相遇，LCA = ancestor[find(w)]。 一次 DFS 即可批次解出所有查詢。