[程式] 最近共同祖先 (Lowest Common Ancestor - LCA)

LCA 算是 tree 滿容易用上的一項特性，原因在於找出任意兩點 u, v 的 LCA 後 (假設是 w)，通常問題可以拆解為：

• (u -> w) + (v -> w): 這樣的兩條路徑各自求解後合併

LCA 的找法可以參考演算法筆記中的 Jump Pointer Algorithm，他的基本概念就是對每個 node 的前 1、2、4、8 ... (2^n) 倍的祖先，如此一來，假設要知道一個 node 的前 5 代祖先是誰，只要知道他的前一代祖先的前四代祖先是誰就可以了。(簡單來說，看成用二進位表示法就知道這種儲存方式可以得知任意一個點的任意一代的祖先囉)

透過這種方法，對任意 2 點 u, v，我們可以知道最後的共同的祖先必然是 root，從上往下追蹤直到出現分歧為止，這就是最近的共同祖先拉。

實作的部分是參考這篇，原因在於 Heavy Light Decomposition 中就會用到 LCA 的概念去拆解問題。


最後的實作如下：