2.2　最近公共祖先LCA

最近公共祖先（Lowest Common Ancestors，LCA）指有根樹中距離兩個節點最近的公共祖先。祖先指從當前節點到樹根路徑上的所有節點。

u和v的公共祖先指一個節點既是u的祖先，又是v的祖先。u和v的最近公共祖先指距離u和v最近的公共祖先。若v是u的祖先，則u和v的最近公共祖先是v。

可以使用LCA求解樹上任意兩點之間的距離。求u和v之間的距離時，若u和v的最近公共祖先為lca，則u和v之間的距離為u到樹根的距離加上v到樹根的距離減去2倍的lca到樹根的距離：dist[u]+dist[v]-2×dist[lca]。

求解LCA的方法有很多，包括暴力搜索法、樹上倍增法、在線RMQ算法、離線Tarjan算法和樹鏈剖分。

在線算法：以序列化方式一個一個地處理輸入，也就是說，在開始時并不需要知道所有輸入，在解決一個問題后立即輸出結果。

離線算法：在開始時已知問題的所有輸入數據，可以一次性回答所有問題。