一、基本概念

在一棵沒有環的樹上，每個節點肯定有其父親節點和祖先節點，而最近公共祖先，就是兩個節點在這棵樹上深度最大的公共的祖先節點。

換句話說，就是兩個點在這棵樹上距離最近的公共祖先節點。

所以LCA主要是用來處理當兩個點僅有唯一一條確定的最短路徑時的路徑。

二、算法

（1）Tarjan/DFS

詳細解釋

?

（2）ST/倍增

?

三、例題

http://acm.hdu.edu.cn/showproblem.php?pid=2586（題解：https://blog.csdn.net/weixin_43272781/article/details/88797017）

https://www.luogu.org/problemnew/show/P3379

http://acm.hdu.edu.cn/showproblem.php?pid=2874（題解：https://blog.csdn.net/weixin_43272781/article/details/88850225）

四、參考文章

https://www.cnblogs.com/JVxie/p/4854719.html

https://www.cnblogs.com/lsdsjy/p/4071041.html

總結

以上是生活随笔為你收集整理的最近公共祖先(Lowest_Common_Ancestors)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。