下载掌阅APP，畅读海量书库
立即打开
最近公共祖先（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算法和树链剖分。
在线算法： 以序列化方式一个一个地处理输入，也就是说，在开始时并不需要知道所有输入，在解决一个问题后立即输出结果。
离线算法： 在开始时已知问题的所有输入数据，可以一次性回答所有问题。