最近公共祖先 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] + dis[v] - 2 * dist[lca]

求解 LCA 的方法有很多，包括暴力搜索法、树上倍增法、在线 RMQ 算法、离线 Tarjan 算法和树链剖分。

在线算法：以序列化方式一个一个的处理输入，也就是说，在开始时并不知道所有的输入，在解决一个问题后立即输出结果。

离线算法：在开始时，已知问题的所有输入数据，可以一次性回答所有问题。

二 暴力搜索法

暴力搜索法有两种：向上标记法和同步前进法。

1 向上标记法

从 u 向上一直到根节点标记所有经过的节点，若 v 已被标记，则 v 节点为 LCA(u,v) ，否则 v 也向上走一步。第 1 次遇到已标记节点时，该节点为 LCA(u,v)。

2 同步前进法

将 u、v 中较深的节点向上走到深度较浅的节点的同一深度，然后两个节点一起向上走，直到走到同一节点，该节点就是 u 和 v 的最近公共祖先。记作 LCA(u,v)。若较深的节点 u 到达 v 的同一深度时，那个节点正好是 v 则节点，则 v 节点为 LCA(u,v) 

3 算法分析

以暴力搜索法求解 LCA，两种方法的时间复杂度在最坏情况下均为 O(n)。