LCA总结_lca复杂度

LCA(Least Common Ancestors) ，即最近公共祖先，在一棵有根树中，找出某两个节点 u 和 v 最近的公共祖先。

LCA可以分为在线算法和离线算法

• 在线算法：指程序可以以序列化的形式一个一个输入，也就是说一开始并不知道所有输入。
• 离线算法：指一开始就知道问题的所有数据，而在解决问题后立即输出结果。

 

 

1.LCA倍增算法 (在线)

时间复杂度：O((n+q)logn) 

转自https://www.cnblogs.com/FuTaimeng/p/5655616.html

倍增算法可以在线求树上两个点的LCA，时间复杂度为nlogn

预处理：通过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;
}

 

 

2.Tarjan算法(离线)

时间复杂度：O(n+q) 

转自：https://blog.csdn.net/riba2534/article/details/77181121

首先来介绍一下 Tarjan 算法的基本思路：

1. 任选一个节点为根节点，从根节点开始
2. 遍历该点 u 的所有子节点 v ，并标记 v 已经被访问过
3. 若 v 还有子节点，返回 2 ，否则下一步
4. 合并 v 到 u 所在集合
5. 寻找与当前点 u 有询问关系的点 e
6. 若 e 已经被访问过，则可以确定 u、e 的最近公共祖先为 e 被合并到的父亲节点

 

 

我们以图示：

假设存在查询： LCA(T,3,4)、LCA(T,4,6)、LCA(T,2,1) 。

我们假设在如下树中模拟 Tarjan 过程

注意：每个节点的颜色代表它当前属于哪一个集合，橙色线条为搜索路径，黑色线条为合并路径。

当前所在位置为 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 = {} ，无相关查询因此该层递归结束。

递归返回，当前所在位置 u = 1 ，合并节点 5 到 u 所在集合，并标记 vis[5] = true ，未遍历孩子集合 v = {} ，遍历相关查询发现存在LCA(T,2,1) ，此时该查询的解便是节点 2 所在集合的首领，即 LCA(T,2,1) = 1 ，递归结束。

至此整个 Tarjan 算法便结束。

 

代码：

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]));
	}
}

 

 

3.DFS + ST 算法(在线)

时间复杂度：O（nlogn）

//带填坑