<i id="yupd0"></i>
  • <i id="yupd0"></i>
  • <thead id="yupd0"></thead>
    <blockquote id="yupd0"></blockquote>
    <i id="yupd0"></i>
  • 碼迷,www.greeshyz.com
    首頁 > 其他好文 > 詳細

    LCA之倍增簡單講解

    時間:2020-07-30 22:20:01      閱讀:56      評論:0      收藏:0      [點我收藏+]

    標簽:height   模板   width   優化   str   iostream   common   tchar   while   

    LCA之倍增簡單講解

    LCA代指Least Common Ancestor,翻譯過來就是最近公共祖先

    如下圖,x和y的最近公共祖先就是二號節點

    技術圖片

     

    那么,如何來求這個最近公共祖先呢?

    1.暴力算法

    讓x和y一步一步向上爬,一直爬到相遇為止

    x: 4->3->2

    y: 6->5->2

    可是這樣暴力實在是太慢了,我們要想辦法優化它

    于是就有了倍增求解LCA

    2.倍增

    倍增的意思就是按二的此方遞增,比如: 1->2->4->8->16......

    在x與y向上爬找祖先時,我們不用每次向上爬一個,而是向上爬2^n個,這樣程序的效率會高很多

    怎么倍增呢?我們需要從大到小跳,比如: 32->16->8->4...... 為什么不是從小到大?應為可能會跳過,出現“悔棋”的情況

    舉個例子:

    技術圖片

     

     

     我們要求x(5號節點)與y(10號節點)的 LCA

    倍增的時候,我們發現y的深度比x的深度要小,于是現將y跳到8號節點,使他們深度一樣:

    技術圖片

     

     

     這個時候,x和y的深度就相同了,于是我們按倍增的方法一起去找LCA

    我們知道n(10)之內最大的二的次方是8,于是我們向上跳8個單位,發現跳過了。

    于是我們將8/2變成4,還是跳過了。

    再將4/2變成2,跳到了0號節點。

    雖然這時跳到了LCA,但是如果直接if(x==y)就確定的話,程序無法判斷是剛好跳到了還是跳過了,應為跳過了x也等于y

    于是我們需要剛好跳到LCA的兒子上,然后判斷if(x的爸爸==y的爸爸)來確定LCA

    由于每一個數都可以分解為幾個2^n的和(不信自己試),所以他們一定會跳到LCA的兒子上

    于是我們就找到了LCA啦!

    3.預處理

    明白了基本思路之后,我們就開始寫程序了

    可是在寫LCA之前,我們還得進行預處理

    要處理些什么呢?

    1.每一個點的深度,以便到時候判斷

    2.每一個點2^i級的祖先,以便到時候倍增跳

    于是我們用一個dep數組來記錄每一個點的深度,再用一個fa[i][j]表示節點i的2^j級祖先

    dep數組的更新就是他爸爸的深度+1,但是如何更新fa數組呢?

    fa[i][j]=fa[fa[i][j-1]][j-1]

    這個式子是什么意思呢?

    fa[i][j]就是i的2^j級祖先,那fa[i][j-1]就是i的2^(j-1)級祖先。

    又因為我們知道2^(j-1)+2^(j-1)=2^j,i的2^(j-1)級祖先的2^(j-1)級祖先 就是i的2^j級祖先。

    這就是這句話的意思。代碼如下:

    void dfs(int x,int father) //x為當前節點,father為他的爸爸
    {
        dep[x]=dep[father]+1; //x的深度是他父親的深度+1
        fa[x][0]=father; //2^0是1,x向上一個的祖先就是他爸爸
        for(int i=1;(1<<i)<=dep[x];i++) //1<<i就是2^i,當2^i小于x的深度時,枚舉他的祖先
        {
            fa[x][i]=fa[fa[x][i-1]][i-1]; //上面說過的fa數組的更新
    }
    for(int i=0;i<e[x].size();i++) //枚舉與他相鄰的邊(我用的是vector存圖) { if(e[x][i]!=father) //如果不是他爸爸 { dfs(e[x][i],x); //繼續dfs } } return; }

    4.LCA主函數

    過程在上面已經講過了,直接上代碼:

    int lca(int u,int v) //u,v就相當于先講的x和y
    {
        int temp; //temp是兩個點的深度度差
        if(dep[u]<dep[v]) //我們默認u的深度大一些,否則將u與v交換
            swap(u,v);
        temp=dep[u]-dep[v]; //計算深度差
        for(int i=0;(1<<i)<=temp;i++) //將u的深度變得與v相同,還是使用倍增的思想
        {
            if((1<<i)&temp) //這個操作就相當于將深度差變成幾個2^n的和,判斷2^i是不是其中一個
            {
                u=fa[u][i]; //將u跳到他祖先的位置
            }
        }
        if(u==v) //如果u剛好等于v,即他們已經變成了同一個點
        {
            return u; //返回這個點的值,就是LCA
        }
        for(int i=(int)(log(n)/log(2));i>=0;i--) //(int)(log(n)/log(2))就是n以內最大的2的次方,從最大的開始倍增
        {
            if(fa[u][i]!=fa[v][i]) //如果他們的爸爸不相同,即沒有找到LCA
            {
                u=fa[u][i]; 
                v=fa[v][i]; //一起倍增
            }
        }
        return fa[u][0]; //返回他們的爸爸,即是LCA   
    }

     5.完整代碼

    下面是模板題洛谷p3379的代碼:

     

    #include <cmath>
    #include <cstdio>
    #include <vector> 
    #include <cstring>
    #include <iostream>
    #include <algorithm>
    using namespace std;
    const int maxn=500005;
    vector <int> e[maxn];
    int n,m,s,dep[maxn],fa[maxn][21];
    int read() //快讀 
    { 
        int ans=0,flag=1;
        char ch=getchar();
        while(!isdigit(ch))
        {
            if(ch==-)
                flag=-1;
            ch=getchar();
        }
        while(isdigit(ch))
        {
            ans=ans*10+ch-0;
            ch=getchar();
        } 
        return ans*flag; 
    } 
    void dfs(int x,int father) //x為當前節點,father為他的爸爸
    {
        dep[x]=dep[father]+1; //x的深度是他父親的深度+1
        fa[x][0]=father; //2^0是1,x向上一個的祖先就是他爸爸
        for(int i=1;(1<<i)<=dep[x];i++) //1<<i就是2^i,當2^i小于x的深度時,枚舉他的祖先
        {
            fa[x][i]=fa[fa[x][i-1]][i-1]; //上面說過的fa數組的更新
        }
        for(int i=0;i<e[x].size();i++) //枚舉與他相鄰的邊(我用的是vector存圖)
        {
            if(e[x][i]!=father) //如果不是他爸爸
            {
                dfs(e[x][i],x); //繼續dfs
            }
        } 
        return;
    }
    int lca(int u,int v) //u,v就相當于先講的x和y
    {
        int temp; //temp是兩個點的深度度差
        if(dep[u]<dep[v]) //我們默認u的深度大一些,否則將u與v交換
            swap(u,v);
        temp=dep[u]-dep[v]; //計算深度差
        for(int i=0;(1<<i)<=temp;i++) //將u的深度變得與v相同,還是使用倍增的思想
        {
            if((1<<i)&temp) //這個操作就相當于將深度差變成幾個2^n的和,判斷2^i是不是其中一個
            { 
                u=fa[u][i]; //將u跳到他祖先的位置
            }
        }
        if(u==v) //如果u剛好等于v,即他們已經變成了同一個點
        {
            return u; //返回這個點的值,就是LCA
        }
        for(int i=(int)(log(n)/log(2));i>=0;i--) //(int)(log(n)/log(2))就是n以內最大的2的次方,從最大的開始倍增
        {
            if(fa[u][i]!=fa[v][i]) //如果他們的爸爸不相同,即沒有找到LCA
            {
                u=fa[u][i]; 
                v=fa[v][i]; //一起倍增
            }
        }
        return fa[u][0]; //返回他們的爸爸,即是LCA   
    }
    int main()
    {
        n=read();
        m=read();
        s=read();
        for(int i=1;i<=n-1;i++)
        {
            int x=read(),y=read();
            e[x].push_back(y);
            e[y].push_back(x); //vector存圖 
        }
        dfs(s,0); //預處理 
        for(int i=1;i<=m;i++)
        {
            int x=read(),y=read();
            int ans=lca(x,y);
            printf("%d\n",ans); 
        }
        return 0; 
    } 

     

    其他題目:

    洛谷p3884 二叉樹問題

    洛谷p2420 讓我們異或吧

    洛谷p3398 倉鼠找sugar

     

    LCA之倍增簡單講解

    標簽:height   模板   width   優化   str   iostream   common   tchar   while   

    原文地址:https://www.cnblogs.com/what-the-heck/p/13397981.html

    (0)
    (0)
       
    舉報
    評論 一句話評論(0
    登錄后才能評論!
    迷上了代碼!
    91色国产论坛,久草99福利资源,青青草在线华人,99热在线视频观看免费,青青草a片免费看,青青草av视频导航,香蕉网站伊人大香蕉 青青碰人青青草免费 国产自拍偷拍在线播放 青青草华人在线av 伊人影院在线大香 无码大香蕉网伊人色 久久大香蕉视频网 青草精品资源在线 伊人大香蕉在线精品 97资源总站久久爱视频 自拍中文字幕 青青草手机在线视频 青青草久久爱大香蕉 国产青青草自拍 伊人大香蕉在线精品 97资源总站久久爱视频 自拍中文字幕 av图片在线看 久草视频福利免费资源站 自拍国产视频在线 www.琪琪色 爱色影爱色搞搞 97资源库 大香萑a久草视频 久草在线福利资站 青青草成人在线免费视频 久久精品国can视频在热 99热国产情侣偷拍 国产自拍 在线 凹凸分类视频97免费 av啪啪中文网站 青青草91自拍视频 奇米影视第四色 国产无限制自拍 大香蕉伊人精品在线 久久手机看片国产免费 无码大香蕉网伊人色 亚洲激情色 久草99福利资源 狼人色终合网站 91色国产色去色 2019奇米777奇米网 久久草妹妹色 米奇影院888奇米色 青青青草成人免费现看 超碰自拍 在线99热这里精品 色琪琪永久无码 伊人大香蕉成人视频综合 国产自拍视频在线 大香蕉伊人久操在线 青青草久草热久久草 偷拍自拍第四色 奇米网电影网 超碰99久久天天拍日日操 天天拍天天拍久草片 激情图片,激情小说 超碰碰av大香蕉伊人 久草97大香蕉伊人 美女伊人色情香蕉网站 青青草华人免费视频在线 大香蕉伊人久草视频 奇米网在线手机在线 青草七次郞视频观看 青青草公开在线观看 狠狠夜夜干大香蕉伊人 777奇米网 日逼视频网站 欧美人和动物XXX 大香蕉色 欧美 国产 奇米影院首页 大香蕉伊人久久爱在线 青青青草免费手机播放 国产青青草 欧美一级黑寡妇夜夜干 啪啪 国产精品 东方aⅴ在线看 手机看A片 777米奇色狠狠俺去啦 香蕉网站伊人中文字幕 久操在线新免费视频 伊人影院在线大香 大香蕉成人伊人在线视频 青青草成人在线视频观看 91国产自拍偷拍视频 青青草色爱久久 精品国产自拍 小色狗 琪琪热热色无码 影音先锋大香蕉久草资源 小明视频看看成人免费 俺去了色网婷婷色 久久色情片 超碰在线青青草 超碰视频起碰视频 国产偷拍自拍影音先锋 小明视频看看成人免费 俺去了色网婷婷色 久久色情片 超碰在线青青草 超碰视频起碰视频 国产偷拍自拍影音先锋 老鸭窝在线视频 www.奇米在线四色 老版本日本怡春院 强奸乱伦在线观看 青青草在观视频 色琪琪在线视频原网 欧美色色大香焦 欧美色热图 亚洲香蕉手机在线观看视频 偷拍偷窥自拍网站 超91在线观看 最新奇米奇色777在线 婷婷网站 微拍秒拍福利视频 自拍在线 精品视频 欧美情色无码在线 久草激情视频 午夜高清影院在线观看 第四色青娱乐奇米影视 青青草在线综合 99热这里有精品 自拍偷拍影音先锋 国产自拍 先锋影音 成人在线视频97 久草在线免费观看大香蕉 99er久久国产精品在线 精品国产在线偷拍 啪啪青青草视频 国内偷拍 亚洲 大香蕉成人手机在线 在线伊人大香蕉手机版 久草伊人久草视频 伊人久久青青草综合网 青青草手机在线视频 青青草久久爱大香蕉 国产青青草自拍 伊人大香蕉在线精品 97资源总站久久爱视频 自拍中文字幕 av图片在线看 久草视频福利免费资源站 自拍国产视频在线 www.琪琪色 爱色影爱色搞搞 97资源库 大香蕉在线视频免费观看 a片直播妹子在线视频 a.v在线视频 开心五月色婷婷免费 香蕉福利视频在线观 青青草成人+激情偷拍 青青草视频大香蕉伊人网 av啪啪中文网站 青青草91自拍视频 奇米影视第四色 国产无限制自拍 大香蕉伊人精品在线 久久手机看片国产免费 无码大香蕉网伊人色 亚洲激情色 久草99福利资源 狼人色终合网站 91色国产色去色 2019奇米777奇米网 久久草妹妹色 米奇影院888奇米色 青青青草成人免费现看 超碰自拍 在线99热这里精品 色琪琪永久无码 伊人大香蕉成人视频综合 国产自拍视频在线 大香蕉伊人久操在线 青青草久草热久久草 偷拍自拍第四色 奇米网电影网 超碰99久久天天拍日日操 天天拍天天拍久草片 激情图片,激情小说 青青草久草热久久草 偷拍自拍第四色 奇米网电影网 超碰99久久天天拍日日操 天天拍天天拍久草片 操好屌色 米奇先锋 久草 偷拍 亚洲,偷拍,自拍,精品 伊人大香蕉综合色 大香蕉久久久 成人色啪啪 大香蕉色看片 欧美自拍在线 久久色综合网站xoxo 久热草大香蕉在线视频 久久大香蕉视频网 肏逼免费视频在线 网友自拍偷拍 欧美 国产 奇米影院首页 大香蕉伊人久久爱在线 青青青草免费手机播放 国产青青草 欧美一级黑寡妇夜夜干 啪啪 国产精品 东方aⅴ在线看 手机看A片 777米奇色狠狠俺去啦 香蕉网站伊人中文字幕 久操在线新免费视频 伊人影院在线大香 大香蕉成人伊人在线视频 青青草成人在线视频观看 91国产自拍偷拍视频 青青草色爱久久 精品国产自拍 小色狗 琪琪热热色无码 影音先锋大香蕉久草资源 小明视频看看成人免费 俺去了色网婷婷色 久久色情片 超碰在线青青草 欧美激情图片 自拍超碰 久草视频在线 天天 综合色伊人网 大香蕉视频成人中文网 大香蕉伊人欧美色 久热在线播放中文字幕 青青草久草福利 欧美色色大香焦 欧美色热图 亚洲香蕉手机在线观看视频 偷拍偷窥自拍网站 超91在线观看 最新奇米奇色777在线 婷婷网站 微拍秒拍福利视频 自拍在线 精品视频 欧美情色无码在线 久草激情视频 午夜高清影院在线观看 第四色青娱乐奇米影视 青青草在线综合 99热这里有精品 自拍偷拍影音先锋 国产自拍 先锋影音 成人在线视频97 久草在线免费观看大香蕉 99er久久国产精品在线
    久久草2019在线观看 99这里有精品 大香蕉免费公开青青草 狠狠色丁香婷婷综合 国产久草福利手机在线 青青草黄色三级网站 大香蕉他也啪 青青草视频大香蕉伊人网 久久爱大香焦在线视频 日本有码视频 成人视屏 国产精品91在线 91国产自拍小视频 伊人狼人香蕉网小说 青青草香蕉草久在线 av青青操 亚洲自拍欧美 91 国产 在线 97超碰资源共享 青青草伊人大香蕉 奇米四色网 国産偷拍91 精品国产在线自拍 伊人大香蕉色琪琪影院 caoprom超碰 青青视频在线视频 开心五月婷婷色婷在线 第四色色 Caoprom超碰视频 亚洲图片欧美图色姐 天天干情色网 操妹妹干妹妹 丁香五月婷婷伊人大香蕉 国产精品自拍偷拍在线 青青青成人社区 成人av在线 碰碰视频在线免费播放 影音先锋 小说色 久久草大香蕉 亚洲情色狼人网 思思久久re热线播放 久久草超碰 播播影院私人影院 大香蕉他也啪 米奇影视 成人国产老鸭窝 伊人大香蕉久久天天啪 男人的天堂 国产精品自偷拍 很很鲁在线97