我的位置:首页 > 资讯>倍增求LCA

倍增求LCA

时间:2020-07-31 15:10:00 来源:互联网 作者: 神秘的大神 字体:

 

本知识点是根据洛谷的P3379(https://www.luogu.com.cn/problem/P3379)为题版写成
 

题目描述

如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。

输入格式

第一行包含三个正整数 N,M,SN,M,S,分别表示树的结点个数、询问的个数和树根结点的序号。

接下来 N-1N1 行每行包含两个正整数 x, yx,y,表示 xx 结点和 yy 结点之间有一条直接连接的边(数据保证可以构成树)。

接下来 MM 行每行包含两个正整数 a, ba,b,表示询问 aa 结点和 bb 结点的最近公共祖先。

输出格式

输出包含 MM 行,每行包含一个正整数,依次为每一个询问的结果。



 

LCA概念

LCA即为树中两个元素的最近公共祖先

就像在这棵树里(建图的网站为https://csacademy.com/app/graph_editor/

 

1  和  2   的LCA为  0;

9  和  5  的LCA为  2;

9  和 10  的LCA为  4;

(看到这里,大家应该能理解LCA的意思了)


LCA求法

主流算法主要有Tarjan算法和倍增算法

可是我太太太太太弱了

所以今天在这里就讲解一下LCA的倍增算法

啥是倍增

我太太弱了,无法描述清楚

如有需要,可参考这位大神超超超超萌的表述

https://blog.csdn.net/dong_qian/article/details/81702697

 

正经求法

最开始的步骤是建图;

于是有了两种建法;

一种使用STL的vector(但可能很慢炸掉,,STL的通病)

vector <int> son[N];

另一种则是acwing上y神长写的邻接表(数组版)

int h[N], e[N], ne[N], idx;

void add(int a, int b,
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

但为了图省事,,,,本蒟蒻偏向于STL,但但但但是,STL会爆炸两个点

所以还是老老实实地写邻接表(链式前项星)吧(泪)

 之后便是算法的!!!精华!!!

 

还是这棵树,

比方说我要求7,10的LCA

我们就先把10和7移到同一深度上也就是把10移至8

之后给出10和7之前所有的father

7的father 1 0  
10(8)的father 4 2 0  

 

 

 

 

然后运用倍增的思想;

也就是说,我们知道10(8)和7之前father的数量;

我们把这个值二进制化

然后由小于这个数的最大的2^n开始

往下尝试直到两个对应的father不等

指向这两个father

之后重复这个操作

直到指向的是同一个节点

这个节点即为所求的最近祖先


当然以上只是整体思路

具体来说,我们先要对这棵树进行预处理

处理出每个节点的深度每个节点的“顶头father”和处于2^n的father

这个过程需要用到一个dfs来遍历

程序如下

void dfs(int k,int ffa)
{
    judge[ffa]=1;//判断这个节点是不是已经被遍历过
    depth[ffa]=depth[k]+1;//更新深度

    fa[ffa][0]=k;//赋“顶头father”的值

    for(int i=1;i<20;i++)
    {
        fa[ffa][i]=fa[fa[ffa][i-1]][i-1];//处理其他“中间father”
    }
    
    for(int i=h[ffa];i!=-1;i=ne[i]) //遍历ffa节点下所有的子节点
    {
    
        if(judge[e[i]])
        {
            continue;//若果被遍历过,跳过(标准dfs内容)
        }
        dfs(ffa,e[i]);//向下遍历
    }
    return;
}

 之后便是我们上述求LCA的思路的实现

int LCA(int a,int b)
{
    if(depth[a]<depth[b])
    {
        swap(a,b);//按顺序排列,方便?
    }
    for(int i=19;i>=0;i--)
    {
        if(depth[a]-(1<<i)>=depth[b])//使a,b到同一深度
            a=fa[a][i];
    }
    if(a==b)
        return a;//如果这是a,b相等直接返回答案
    for(int i=19;i>=0;i--)
    {
        if(fa[a][i]!=fa[b][i])
            a=fa[a][i],b=fa[b][i];//按照倍增思想往上枚举
            
    }
    return fa[a][0];//返回答案
}

 

主程序也来一下

int main()
{
    cin>>n>>m>>s;
        memset(h,-1,sizeof(h));//邻接表预处理
    for(int i=1;i<n;i++)
    {
        cin>>a>>b;
        add(a,b);
        add(b,a);//输入
    }
    
    
    depth[0]=-1;//方便给每个节点的深度赋值
    
    dfs(0,s);//深搜深搜

    for(int i=1;i<=m;i++)
    {
        cin>>a>>b;
        cout<<LCA(a,b)<<endl;//直接快乐的把返回值输出
    }
}
     

恭喜你,AC了!!!


 


 

标程呈现(方便复制粘贴然后ac) 

#include<bits/stdc++.h>
using namespace std;
int n,m,s;
const int N=500010;
//vector<int>  tre[N];
int ne[N*2],e[N*2],h[N],idx;
void add (int a,int b)
{
    e[idx]=b;
    ne[idx]=h[a];
    h[a]=idx++;
}
int  depth[N],fa[N][20],in[N],a,b;
bool judge[N];

void dfs(int k,int ffa)
{
    judge[ffa]=1;
    depth[ffa]=depth[k]+1;

    fa[ffa][0]=k;

    for(int i=1;i<20;i++)
    {
        fa[ffa][i]=fa[fa[ffa][i-1]][i-1];
    }
    
    for(int i=h[ffa];i!=-1;i=ne[i])
    {
    
        if(judge[e[i]])
        {
            continue;
        }
        dfs(ffa,e[i]);
    }
    return;
}

int LCA(int a,int b)
{
    if(depth[a]<depth[b])
    {
        swap(a,b);
    }
    for(int i=19;i>=0;i--)
    {
        if(depth[a]-(1<<i)>=depth[b])
            a=fa[a][i];
    }
    if(a==b)
        return a;
    for(int i=19;i>=0;i--)
    {
        if(fa[a][i]!=fa[b][i])
            a=fa[a][i],b=fa[b][i];
            
    }
    return fa[a][0];
}



int main()
{
    cin>>n>>m>>s;
memset(h,-1,sizeof(h));
    for(int i=1;i<n;i++)
    {
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    
    int t=0;
    depth[0]=-1;
    
    dfs(0,s);

    for(int i=1;i<=m;i++)
    {
        cin>>a>>b;
        cout<<LCA(a,b)<<endl;
    }
}
 

 

 

快乐,,结束


 

ps:

我实在太太太弱了(尽管我喜欢自称朕)

我改了两个小时才改对

提醒大家注意

  1. 注意h【】数组赋值的位置,,要在add之前啊啊啊啊
  2. 注意添加边的时候添加的是双向边,不然会有可能(一定)不能完成遍历
  3. fa数组的递归式请记牢(抄对)

感谢<img src="https://www.cnblogs.com/skins/custom/images/logo.gif" alt="返回主页" id="blogLogo" class="img-responsive">zhouzhendong大佬的博客给予我的引导

在此标注地址https://www.cnblogs.com/zhouzhendong/p/Least-Common-Ancestors.html

<span style="font-size: 14px;"></span>


还有一些无关紧要的话<br>

如果有小伙伴乐意看看本蒟蒻有多弱的话

点击下方链接看看我的洛谷主页

https://www.luogu.com.cn/user/159708

欢迎来访(卖萌)

 

最后随机地附上一首诗

 

切丽塔


Roberto Bolano

在精华中生活着切丽塔

在纯粹观念和香水之间

消瘦的无产者身体

从现在起永远流浪

似乎智利在欧洲的一个影子

永远追不上手造的那个词

或死水的留言

或爱与天真的梦