一、基本概念

在一棵没有环的树上，每个节点肯定有其父亲节点和祖先节点，而最近公共祖先，就是两个节点在这棵树上深度最大的公共的祖先节点。

换句话说，就是两个点在这棵树上距离最近的公共祖先节点。

所以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