前言

今天开始做noi p 难度的天天爱跑步这道题。虽然我现在还并没有把它杠掉，但是由于学到一种新式LCA找法，于是心血来潮写下了这篇博文。本文中的LCA找法均来自本人学过或听说过的算法。

正文

①倍增

用倍增算法解决LCA时，以数组fa[i][j]表示以节点i开始，向上跳2^j个点所达到的位置。 计算fa数组时，先从小到大枚举2的次方数j，再枚举每一个点i，fa[fa[i]][j-1]即为fa[i][j]的值。 具体实现可参考本人博文货车运输

②tarjan

本人仅仅是听说过tarjan这种万能的算法可以求LCA，然而并没有学过，也懒得学辣，所以度娘出一篇文章供大家参考。见这里

③树链剖分

这才是本文最想介绍的一种算法。 如果没有学过树链剖分，本人安利一个不错的视频click here 由于树链剖分将完整的树剖成了一条条互不重复的链，并且记录了当前链的顶部和当前点的父亲，所以我们可以利用这种性质进行求解。 具体实现： ①当两个点的top值不同时，即两个点不在同一条链内，比较两个点的top的deep，将其中top的deep值较大的那个点跳到top的父亲处，重复①。否则进行②。 ②返回两个点中deep值较小的那个点的位置，求解完毕。 是不是很短？

就是这么短！ 为什么是正确的呢？ 自己画几个图感受一下就明白辣 当两个点不在同一条链中的时候，两个点永远不可能重合，也就不在其LCA处。 其他的我就不用解释了叭！

最后

本人介绍了三种LCA的求解方法，推荐树链剖分的方法。普及组小盆友请随意选择 貌似普及组考纲中并没有LCA这个考点嘛

The end.