求解 LCA の方法

这篇具有很好参考价值的文章主要介绍了求解 LCA の方法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

最近公共祖先(LCA)

最近公共祖先简称 LCA(Lowest Common Ancestor)。两个节点的最近公共祖先,就是这两个点的公共祖先里面,离根最远的那个。
-----oi wiki

举个例子

求解 LCA の方法

在这张图中,\(5\)\(9\) 的最近公共祖先就是 \(3\)\(9\)\(7\) 的最近公共祖先就是 \(2\)

由于在树上两点间的简单路径是唯一的,并且从上图中我们可以很容易发现两点的 LCA 一定在其的简单路径上,所以我们有时候需要求出某两个点的 LCA

P3379 【模板】最近公共祖先(LCA)

以下所有的测试数据输入输出皆保持一致

暴力跳

最暴力的算法一个一个往上跳,复杂度 \(O(TLE)\)

没写,因为会 T

倍增求 LCA

这个方法是最简单也是最好想的一个方法,而且支持在线的查询,时间复杂度为 \(O(m\log n)\),本人看来是暴力的一个优化

我们维护一个 \(f[i][j]\) 数组表示 \(i\) 点往上跳 \(2^{j}\) 所到达的点的编号,\(dep[i]\) 表示 \(i\) 号点在树中的深度

我们首先要做的就是 DFS 一遍把我们的 \(f\)\(dep\) 数组求出来,然后在查询的时候,按照下面的步骤:

  1. 我们首先判断两个点的深度大小,保证传入的 \(x\) 的深度大于 \(y\) 的深度

  2. 我们让 \(x\) 点开始往上跳,从大到小枚举 \(f\) 数组的第二维,只要跳完之后深度大于等于 \(y\) 的深度就跳,这样最后我们使 \(x\)\(y\) 来到了同一高度。

  3. 我们让 \(x\)\(y\) 一起向上跳,前提是两点跳完后不在同一位置,因为跳的时候可能会跳超,但是两点的编号相同,造成是公共祖先但不是最近的情况,最后我们得到了两点的最近公共祖先下方的两个点 \(x'\)\(y'\),这个时候直接返回其中一个的父节点即可。

注意第二步完成之后需要特判一下,是否两点编号相等,相等直接返回即可,防止两点在同一链上的情况

code:

#include<bits/stdc++.h>
#define N 500010
using namespace std;
struct sb{int t,nex;}e[N<<1];//t存放终点,nex存放下一个边 
int head[N],tot;//head存放头节点,tot存放建边数量 
int de[N],f[N][22],lg[N];//de存放每一个点的深度,f存放每一个点第2的i次方的祖先,lg存放log值 
inline void add(int x,int y)//存边函数 
{
	e[++tot].t=y;//存放终点 
	e[tot].nex=head[x];//存放下一个边的头节点 
	head[x]=tot;//更新
}
inline void dfs(int now,int fa)//深搜函数 
{
	f[now][0]=fa;//当前节点上一个祖先就是fa 
	de[now]=de[fa]+1;//当前节点的深度就是祖先的深度加一 
	for(int i=1;i<=lg[de[now]];i++)//从2的1次方开始循环 
	  f[now][i]=f[f[now][i-1]][i-1];//当前点的第2的i次方个祖先就是从当前的点的第i-1次方祖先的2的i-1次方的祖先 
	for(int i=head[now];i;i=e[i].nex)//寻找和当前点相连的点 
	  if(e[i].t!=fa)dfs(e[i].t,now);//如果终点不是祖先的话就继续深搜 
}
inline int LCA(int x,int y)//寻找最近公共祖先 
{
	if(de[x]<de[y])swap(x,y);//如果x的深度小于y的深度就把xy的值互换 
	while(de[x]>de[y])//只要x的深度大于y 
	  x=f[x][lg[de[x]-de[y]]-1];//先让x跳到和y一样的深度 
	if(x==y)return y;//如果两个点相等说明y是x的祖先,直接返回y 
	for(int k=lg[de[x]];k>=0;k--)
{
	  if(f[x][k]==f[y][k])continue;//因为是跳到LCA下面的一层,所以他们一定不相等, 
	    x=f[x][k],y=f[y][k];//替换xy的值继续循环 
}
	return f[x][0];//返回当前x的祖先即为最近公共祖先 
}
int main()
{
	int n,m,d;//n个点,m次询问,d为根节点 
	scanf("%d%d%d",&n,&m,&d);
	for(int i=1;i<=n-1;i++)//从第一个到最后一个 
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);//存边 
		add(y,x);//无向图存两次 
	}
	for(int i=1;i<=n;i++)//预处理log的值 
	  lg[i]=lg[i-1]+(1<<lg[i-1]==i);//计算 
	dfs(d,0);//深搜处理出f和de的值 
	for(int i=1;i<=m;i++)//开始询问 
	{
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d\n",LCA(x,y));//输出最近公共祖先 
	}
	return 0;//好习惯 
}

求解 LCA の方法

tarjan 求 LCA

这个算法在 \(n,m\) 差不多的时候是比较快的,因为他复杂度是 \(O(n+m)\) 的,可惜的是只能离线。

我们对于每一个询问的两点之间连一条无向边(并不是在存树的数组里面连边)

在 DFS 的过程中,给走过的节点打上标记,同时维护并查集,如果 \(u\) 节点的这棵子树没搜完,那么 \(fa[u] = u\);,搜完后再更新并查集。

我们假设查询 \(u\)\(v\) 的最近公共祖先,搜到节点 \(u\),如果另一个节点 \(v\) 已经被搜到过了,那么 \(v\) 点的并查集祖先就是 \(u\)\(v\) 的最近公共祖先。

我们来模拟一下用 tarjan 求 LCA 的样例

求解 LCA の方法

我们在 DFS 的时候,首先来到 \(4\) 号点,然后我们 \(vis[4]=1\),将两个子节点都合并到 \(4\) 号点上,发现有一组询问 \(4,5\) 但是 \(vis[5]=0\) 所以不能确定 LCA

然后来到 \(2\),将 \(vis[2]=1\) 发现没法往下走,所以不走了,发现有 \((3,2)\)\((1,2)\) 两组询问,但 \(vis[3]=0\)\(vis[1]=0\) 所以不能确定 LCA

然后来到 \(1\),将 \(vis[1]=1\),将子节点合并到 \(1\) 号点,发现有询问 \((1,2)\),这个时候 \(vis[2]=1\) 所以我们能确定 LCA,直接返回 \(fid(2)\),也就是 \(4\)

然后来到 \(3\),将 \(vis[3]=1\),没有子节点,发现有询问 \((3,2)(3,5)\),这时候 \(vis[2]=1,vis[5]=0\),所以能确定第一个询问的 LCA,记录 LCA\((3,2)=fid(2)=4\)

然后来到 \(5\),将 \(vis[5]=1\),发现有询问 \((3,5)(4,5)\),我们发现两个都可以确定,记录 LCA\((3,5)=fid(3)=1\), LCA\((4,5)=fid(4)=4\)

至此算法结束。

有的人可能会问,要是出现下面的情况怎么办?

求解 LCA の方法

要是查 \((1,2)\) 的话,不就会返回 \(fid(2)\) 递归下去不就是 \(6\) 了吗?

注意我们是在子树全遍历完才会修改当前点的 \(f\) 的值,所以不会出现这个情况

code:

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define N 2000100
using namespace std;
int n,m,s,fa[N],vis[N],head[N],cnt,Head[N],cnt1=1;
struct sb{int u,v,next,lca;}e[N],e1[N];
inline void add(int u,int v){e[++cnt].v=v;e[cnt].next=head[u];head[u]=cnt;}
inline void Add(int u,int v){e1[++cnt1].v=v;e1[cnt1].next=Head[u];Head[u]=cnt1;}
inline int fid(int x){if(fa[x]==x)return x;return fa[x]=fid(fa[x]);}
inline int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){f=ch!='-';ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return f?x:-x;}
inline void DFS(int x,int f)
{
    vis[x]=1;
    for(int i=head[x];i;i=e[i].next)
    {
        int v=e[i].v;
        if(v==f)continue;
        if(!vis[v])DFS(v,x),fa[v]=x;
    }
    for(int i=Head[x];i;i=e1[i].next)
    {
        int v=e1[i].v;
        if(vis[v])e1[i].lca=e1[i^1].lca=fid(v);
    }
}
signed main()
{
    n=read(),m=read(),s=read();
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=n-1;i++)
    {
        int u=read(),v=read();
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        Add(u,v);
        Add(v,u);
    }
    DFS(s,0);
    for(int i=2;i<=cnt1;i+=2)
        cout<<e1[i].lca<<endl;
    return 0;
}
/*
6 1 6
6 4
3 1
2 4
5 1
1 4
1 2
*/

求解 LCA の方法

树链剖分

推销自己的博客

以后我会重修的

首先我们就是要进行两遍 dfs 把 \(dep,f,siz,son,top\) 数组给处理出来,他们分别表示当前点的深度,当前点的父节点,以当前点为根的子树大小,当前点的重儿子编号,当前点所在的链的链头元素。

我们处理完之后,我们根据两点的深度大小来往上跳,和倍增一样,我们要防止跳超了,所以跳完以后两个点的 \(top\) 数组相等就说明已经有一个点的链头元素为两个点的 LCA,然后我们直接返回即可。

注意在跳的时候并不用保证谁比谁深度大,因为跳的时候是两个交替着跳,所以没必要

code:

#include <bits/stdc++.h>
#define N 1000100
#define endl '\n'
using namespace std;
struct sb{int u,v,next;}e[N];
int dep[N],fa[N],siz[N],head[N],son[N],rt,n,m,cnt,top[N];
inline void add(int u,int v){e[++cnt].u=u;e[cnt].v=v;e[cnt].next=head[u];head[u]=cnt;}
inline int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){f=ch!='-';ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return f?x:-x;}
inline void dfs1(int x,int deep,int f)
{
    dep[x]=deep;fa[x]=f;siz[x]=1;
    int maxn=-1;
    for(int i=head[x];i;i=e[i].next)
    {
        if(e[i].v!=f)
        {
            dfs1(e[i].v,deep+1,x);
            siz[x]+=siz[e[i].v];
            if(siz[e[i].v]>maxn)maxn=siz[e[i].v],son[x]=e[i].v;
        }
    }
    return ;
}
inline void dfs2(int x,int tp)
{
    top[x]=tp;
    if(!son[x])return ;
    dfs2(son[x],tp);
    for(int i=head[x];i;i=e[i].next)
        if(e[i].v!=fa[x]&&e[i].v!=son[x])dfs2(e[i].v,e[i].v);
    return ;
}
inline int LCA(int x,int y)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]>=dep[top[y]])x=fa[top[x]];
        else y=fa[top[y]];
    }
    return dep[x]<dep[y]?x:y;
}
signed main()
{
    n=read();m=read(),rt=read();
    for(int i=1;i<=n-1;i++)
    {
    	int u=read(),v=read();
		add(u,v);add(v,u); 
	}
    dfs1(rt,0,rt);
    dfs2(rt,rt);
    for(int i=1;i<=m;i++)cout<<LCA(read(),read())<<endl;
    return 0;
}

求解 LCA の方法

其他算法

由于本人实在太弱所以只整理了前面的三种

其实也可以用 DFS 序来求 LCA,可以去看看魏老师的博客:https://www.luogu.com.cn/blog/AlexWei/leng-men-ke-ji-dfs-xu-qiu-lca

也可以用欧拉序来求 LCA,比如:https://www.luogu.com.cn/blog/shenhy1205/solution-p3379

或者转化为 RMQ 问题求解:https://www.cnblogs.com/cj-xxz/p/11142232.html

或者用 LCT :https://www.luogu.com.cn/blog/surf/solution-p3379文章来源地址https://www.toymoban.com/news/detail-432516.html

到了这里,关于求解 LCA の方法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Lintcode 3715 · Lowest Common Ancestor V (最小祖先好题)

    3715 · Lowest Common Ancestor VPRE Algorithms Medium This topic is a pre-release topic. If you encounter any problems, please contact us via “Problem Correction”, and we will upgrade your account to VIP as a thank you. Description Given a binary tree with a root node root and an array nodes of objects of class TreeNode, you need to find the Lowest Commo

    2024年02月07日
    浏览(26)
  • DAY23:二叉树(十三)二叉树的最近公共祖先+二叉搜索树的最近公共祖先

    一定要仔细看 提示 ,二叉树 数值不重复 ,意味着后序遍历不会存在两边找到了同个元素的情况 本题需要进一步理解后序遍历, 可以认为后序遍历在\\\"深入\\\"到每个子树的最深层之后,才开始\\\"回溯\\\"并访问节点 。 在某种意义上,这可以被视为从下往上的遍历方式 , 但需要注

    2024年02月09日
    浏览(44)
  • 「学习笔记」tarjan 求最近公共祖先

    Tarjan 算法是一种 离线算法 ,需要使用并查集记录某个结点的祖先结点。 并没有传说中的那么快。 将询问都记录下来,将它们建成正向边和反向边。 在 dfs 的过程中,给走过的节点打上标记,同时维护并查集,这里利用了回溯的思想,如果 (u) 节点的这棵子树没搜完,那么

    2024年02月01日
    浏览(49)
  • 「学习笔记」tarjan求最近公共祖先

    Tarjan 算法是一种 离线算法 ,需要使用并查集记录某个结点的祖先结点。 并没有传说中的那么快。 将询问都记录下来,将它们建成正向边和反向边。 在 dfs 的过程中,给走过的节点打上标记,同时维护并查集,这里利用了回溯的思想,如果 (u) 节点的这棵子树没搜完,那么

    2024年02月01日
    浏览(40)
  • 力扣236——二叉树的最近公共祖先

    祝大家新年快乐呀,虽这段时间正值过年,但是我们不要忘记停下学习的脚步。今天我们一起看一到力扣上的经典二叉树OJ题,求二叉树两个结点最近的公共祖先。 https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/description/ 链接给大家放在这里啦,大家一点即达 首先我们

    2024年02月20日
    浏览(42)
  • leetcode 236. 二叉树的最近公共祖先

            这道题是道面试高频题,并且有点抽象。         首先确定终止条件。如果根节点为空,或者其中一个节点是根节点本身(即 p == root 或 q == root ),那么根节点就是它们的最低共同祖先,因此我们直接返回根节点 root 。          接下来,递归调用 lowestComm

    2024年02月15日
    浏览(38)
  • leetcode热题100. 二叉树的最近公共祖先

    Problem: 236. 二叉树的最近公共祖先 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先

    2024年01月19日
    浏览(41)
  • 力扣labuladong一刷day39天最近公共祖先问题

    力扣labuladong一刷day39天最近公共祖先问题 一、236. 二叉树的最近公共祖先 题目链接:https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/ 思路:寻找最近公共祖先,在前序的位置判断,如果找到一个就返回,然后在后序的位置收尾,即左右子树都遍历过了,如果都找到的话

    2024年02月04日
    浏览(38)
  • LeetCode235. 二叉搜索树的最近公共祖先

    235. 二叉搜索树的最近公共祖先 一、题目 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个结点 p、q,最近公共祖先表示为一个结点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大( 一个节点也可以是

    2024年02月12日
    浏览(36)
  • 236. 二叉树的最近公共祖先 ——【Leetcode每日一题】

    给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p 、 q ,最近公共祖先表示为一个节点 x ,满足 x 是 p 、 q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。” 示例 1: 输入:root

    2023年04月26日
    浏览(35)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包