LCA总结
概述篇
LCA (Least Common Ancestors) ，即最近公共祖先，是指这样的一个问题：在一棵有根树中，找出某两个节点 u 和 v 最近的公共祖先。
LCA 可分为在线算法与离线算法
- 在线算法：指程序可以以序列化的方式一个一个处理输入，也就是说在一开始并不需要知道所有的输入。
- 离线算法：指一开始就需要知道问题的所有输入数据，而在解决一个问题后立即输出结果。
算法篇
介绍几种比较高效的算法来解决这一问题，常见的算法有三种：在线 DFS + ST 算法、倍增算法、离线 Tarjan 算法。
在线 DFS + ST 算法
关于 LCA 的这种在线算法也是可以建立在 RMQ 问题的基础上
我们设 LCA(T,u,v) 为在有根树 T 中节点 u、v 的最近公共祖先， RMQ(A,i,j) 为线性序列 A 中区间 [i,j] 上的最小（大）值。
如下图这棵有根树：
我们令节点编号满足父节点编号小于子节点编号（编号条件）
可以看出 LCA(T,4,5) = 2, LCA(T,2,8) = 1, LCA(T,3,9) = 3 。
设线性序列 A 为有根树 T 的中序遍历，即 A = [4,2,5,1,8,6,9,3,7] 。
由中序遍历的性质我们可以知道，任意两点 u、v 的最近公共祖先总在以该两点所在位置为端点的区间内，且编号最小。
举个例子：
假设 u = 8, v = 7 ，则该两点所确定的一段区间为 [8,6,9,3,7] ，而区间最小值为 3 ，也就是说，节点 3 为 u、v 的最近公共祖先。
解决区间最值问题我们可以采用 RMQ 问题中的 ST 算法 。
但是在有些问题中给出的节点并不一定满足我们所说的父节点编号小于子节点编号，因此我们可以利用节点间的关系建图，然后采用前序遍历来为每一个节点重新编号以生成线性序列 A ，于是问题又被转化为了区间最值的查询，和之前一样的做法咯~
时间复杂度： n×O(logn)n×O(logn) 预处理 + O(1)O(1) 查询
我们如何将一个线性序列转化为满足编号条件的有根树呢？
设序列中的最小值为 AkAk ，建立优先级为 AkAk 的根节点 TkTk
将 A[1...k−1]A[1...k−1] 递归建树作为 TkTk 的左子树
将 A[k+1...n]A[k+1...n] 递归建树作为 TkTk 的右子树
读者可以试着利用此方法将之前的线性序列 A = [4,2,5,1,8,6,9,3,7] 构造出有根树 T ，结果一定满足之前所说的编号条件，但却不一定唯一。
离线 Tarjan 算法
Tarjan 算法是一种常见的用于解决 LCA 问题的离线算法，它结合了深度优先搜索与并查集，整个算法为线性处理时间。
首先来介绍一下 Tarjan 算法的基本思路：
- 任选一个节点为根节点，从根节点开始
- 遍历该点 u 的所有子节点 v ，并标记 v 已经被访问过
- 若 v 还有子节点，返回 2 ，否则下一步
- 合并 v 到 u 所在集合
- 寻找与当前点 u 有询问关系的点 e
- 若 e 已经被访问过，则可以确定 u、e 的最近公共祖先为 e 被合并到的父亲节点
void find(int x)
{
if(pre[x]!=x)
pre[x]=find(pre[x]);
return pre[x];
}
void union1(int x,int y)
{
int fx,int fy;
if(fx!=fy)
{
pre[fx]=ty;
}
}
void Tarjan(int u,int fa)
{
for(int i=head[u];i!=-1;i=side[i].next)
{
int v=side[i].id;
if(v==fa) continue;
Tarjan(v,u);
union1(u,v);
}
book[u]=1;
for(int i=0;i<v[u].size();i++)//v[u][i]表示查询u与v[u][i]的LCA
{
if(book[v[u][i]])
printf("%d 和 %d 的LCA是 %d\n",u,v[u][i],find(v[u][i]));
}
}我们假设在如下树中模拟 Tarjan 过程
存在查询： LCA(T,3,4)、LCA(T,4,6)、LCA(T,2,1) 。
注意：每个节点的颜色代表它当前属于哪一个集合，橙色线条为搜索路径，黑色线条为合并路径。
当前所在位置为 u = 1 ，未遍历孩子集合 v = {2,5} ，向下遍历。
当前所在位置为 u = 2 ，未遍历孩子集合 v = {3,4} ，向下遍历。
当前所在位置为 u = 3 ，未遍历孩子集合 v = {} ，递归到达最底层，遍历所有相关查询发现存在 LCA(T,3,4) ，但是节点 4 此时标记未访问，因此什么也不做，该层递归结束。
递归返回，当前所在位置 u = 2 ，合并节点 3 到 u 所在集合，标记 vis[3] = true ，此时未遍历孩子集合 v = {4} ，向下遍历。
当前所在位置 u = 4 ，未遍历孩子集合 v = {} ，遍历所有相关查询发现存在 LCA(T,3,4) ，且 vis[3] = true ，此时得到该查询的解为节点3 所在集合的首领，即 LCA(T,3,4) = 2 ；又发现存在相关查询 LCA(T,4,6) ，但是节点 6 此时标记未访问，因此什么也不做。该层递归结束。
递归返回，当前所在位置 u = 2 ，合并节点 4 到 u 所在集合，标记 vis[4] = true ，未遍历孩子集合 v = {} ，遍历相关查询发现存在LCA(T,2,1) ，但是节点 1 此时标记未访问，因此什么也不做，该层递归结束。
递归返回，当前所在位置 u = 1 ，合并节点 2 到 u 所在集合，标记 vis[2] = true ，未遍历孩子集合 v = {5} ，继续向下遍历。
当前所在位置 u = 5 ，未遍历孩子集合 v = {6} ，继续向下遍历。
当前所在位置 u = 6 ，未遍历孩子集合 v = {} ，遍历相关查询发现存在 LCA(T,4,6) ，且 vis[4] = true ，因此得到该查询的解为节点 4所在集合的首领，即 LCA(T,4,6) = 1 ，该层递归结束。
递归返回，当前所在位置 u = 5 ，合并节点 6 到 u 所在集合，并标记 vis[6] = true ，未遍历孩子集合 v = {} ，无相关查询因此该层递归结束。
3.LCA倍增
倍增算法可以在线求树上两个点的LCA
预处理：通过dfs遍历，记录每个节点到根节点的距离dist[u]，深度d[u]
init()求出树上每个节点u的2^i祖先p[u][i]
求最近公共祖先，根据两个节点的的深度，如不同，向上调整深度大的节点，使得两个节点在同一层上，如果正好是祖先结束，否则，将连个节点同时上移，查询最近公共祖先。
void dfs(int u){
for(int i=head[u];i!=-1;i=edge[i].next){
int to=edge[i].to;
if(to==p[u][0])continue;
d[to]=d[u]+1;
dist[to]=dist[u]+edge[i].w;
p[to][0]=u; //p[i][0]存i的父节点
dfs(to);
}
}
void init(){
for(int j=1;(1<<j)<=n;j++){
for(int i=1;i<=n;i++){
p[i][j]=p[p[i][j-1]][j-1];
}
}
}
int lca(int a,int b){
if(d[a]>d[b])swap(a,b); //b在下面
int f=d[b]-d[a];//f是高度差
for(int i=0;(1<<i)<=f;i++){//(1<<i)&f找到f化为2进制后1的位置，移动到相应的位置
if((1<<i)&f)b=p[b][i];//比如f=5(101),先移动2^0祖先，然后再移动2^2祖先
}
if(a!=b){
for(int i=(int)log2(N);i>=0;i--){
if(p[a][i]!=p[b][i]){//从最大祖先开始，判断a,b祖先，是否相同
a=p[a][i]; b=p[b][i];//如不相同，a b同时向上移动2^j
}
}
a=p[a][0];//这时a的father就是LCA
}
return a;
}转自：https://blog.****.net/qq_28954601/article/details/76856187