最近公共祖先LCA

概述

求最近公共祖先一共有3种算法：

• 离线Tarjan算法,复杂度为:O(n+q)
• 在线ST算法，把lca转换成rmq,复杂度为：O(NlogN)
• 在线倍增算法，利用二进制加速找的过程,复杂度:O(NlogN)

下面只写Tarjan和倍增算法，以洛谷的模板题:P3379 【模板】最近公共祖先（LCA）为例

题目有时候要求求出两个点之间的最短路，当使用离线Tarjan算法的时候，只需要用一个dis数组利用dfs来处理出路径的长度就可以。而使用在线倍增算法的时候，直接在倍增里面的dfs处理一下路径，答案显而易见，就是:dis[u]+dis[v]-2*dis[lca(u,v)]