最近公共祖先(LCA-tarjan/RMQ/倍增)

在一棵没有环的树上，每个节点肯定有其父亲节点和祖先节点，而最近公共祖先，就是两个节点在这棵树上深度最大的公共的祖先节换句话说，就是两个点在这棵树上距离最近的公共祖先节点。
有人可能会问：那他本身或者其父亲节点是否可以作为祖先节点呢？答案是肯定的，很简单，按照人的亲戚观念来说，你的父亲也是你的祖先，而LCA还可以将自己视为祖先节点。
求LCA算法常用的三种tarjan/倍增/ST

tarjan求LCA原理：

声明下面内容参考：大佬传送门https://www.cnblogs.com/JVxie/p/4854719.html
　举个例子吧，如下图所示４和５的最近公共祖先是２，５和３的最近公共祖先是１，２和１的最近公共祖先是１。　

这就是最近公共祖先的基本概念了，那么我们该如何去求这个最近公共祖先呢？

什么是Tarjan(离线)算法呢？顾名思义，就是在一次遍历中把所有询问一次性解决，所以其时间复杂度是O(n+q)。

Tarjan算法的优点在于相对稳定，时间复杂度也比较居中，也很容易理解。

下面详细介绍一下Tarjan算法的基本思路：

1. 任选一个点为根节点，从根节点开始。

2.遍历该点u所有子节点v，并标记这些子节点v已被访问过。

3.若是v还有子节点，返回2，否则下一步。

4.合并v到u上。

5.寻找与当前点u有询问关系的点v。

6.若是v已经被访问过了，则可以确认u和v的最近公共祖先为v被合
并到的父亲节点a。

遍历的话需要用到dfs来遍历(我相信来看的人都懂吧...)，至于合并，最优化的方式就是利用并查集来合并两个节点。

void dfs(int u)
{
    vis[u]=1;
    for(int i=0;i<ve[u].size();i++)//遍历子节点
    {
        int v=ve[u][i];
        dfs(ve[u][i]);//还有子节点
        ouin(u,ve[u][i]);//合并父子节点
    }
    for(int j=0;j<pp[u].size();j++)//寻找当前点u有询问关系的点
    {
        int w=pp[u][j];
        if(vis[w]==1)//如果点已经被访问，就确认父节点是谁
        {
            ans=find(w);
        }
    }
}

建议拿着纸和笔跟着我的描述一起模拟！！

假设我们有一组数据 9个节点 8条边联通情况如下：

1--2，1--3，2--4，2--5，3--6，5--7，5--8，7--9 即下图所示的树

设我们要查找最近公共祖先的点为9--8，4--6，7--5，5--3；

设f[]数组为并查集的父亲节点数组，初始化f[i]=i，vis[]数组为是否访问过的数组，初始为0;

下面开始模拟过程：

取1为根节点，往下搜索发现有两个儿子2和3；

先搜2，发现2有两个儿子4和5，先搜索4，发现4没有子节点，则寻找与其有关系的点；

发现6与4有关系，但是vis[6]=0，即6还没被搜过，所以不操作；

发现没有和4有询问关系的点了，返回此前一次搜索，更新vis[4]=1；

表示4已经被搜完，更新f[4]=2，继续搜5，发现5有两个儿子7和8;

先搜7，发现7有一个子节点9，搜索9，发现没有子节点，寻找与其>有关系的点；

发现8和9有关系，但是vis[8]=0,即8没被搜到过，所以不操作；

发现没有和9有询问关系的点了，返回此前一次搜索，更新vis[9]=1；

表示9已经被搜完，更新f[9]=7，发现7没有没被搜过的子节点了，寻找>与其有关系的点；

发现5和7有关系，但是vis[5]=0，所以不操作；

发现没有和7有关系的点了，返回此前一次搜索，更新vis[7]=1；

表示7已经被搜完，更新f[7]=5，继续搜8，发现8没有子节点，则寻找与其有关系的点；

发现9与8有关系，此时vis[9]=1，则他们的最近公共祖先为>find(9)=5；

(find(9)的顺序为f[9]=7-->f[7]=5-->f[5]=5 return 5;)

发现没有与8有关系的点了，返回此前一次搜索，更新vis[8]=1；

表示8已经被搜完，更新f[8]=5，发现5没有没搜过的子节点了，寻找与其有关系的点；

发现7和5有关系，此时vis[7]=1，所以他们的最近公共祖先为find(7)=5；

(find(7)的顺序为f[7]=5-->f[5]=5 return 5;)

又发现5和3有关系，但是vis[3]=0，所以不操作，此时5的子节点全
部搜完了；

返回此前一次搜索，更新vis[5]=1，表示5已经被搜完，更新f[5]=2；

发现2没有未被搜完的子节点，寻找与其有关系的点；

又发现没有和2有关系的点，则此前一次搜索，更新vis[2]=1；

表示2已经被搜完，更新f[2]=1，继续搜3，发现3有一个子节点6；

搜索6，发现6没有子节点，则寻找与6有关系的点，发现4和6有关系；

此时vis[4]=1，所以它们的最近公共祖先为find(4)=1;

(find(4)的顺序为f[4]=2-->f[2]=2-->f[1]=1 return 1;)

发现没有与6有关系的点了，返回此前一次搜索，更新vis[6]=1，表示6已>经被搜完了；

更新f[6]=3，发现3没有没被搜过的子节点了，则寻找与3有关系的点；

发现5和3有关系，此时vis[5]=1，则它们的最近公共祖先为>find(5)=1；

(find(5)的顺序为f[5]=2-->f[2]=1-->f[1]=1 return 1;)

发现没有和3有关系的点了，返回此前一次搜索，更新vis[3]=1；

更新f[3]=1，发现1没有被搜过的子节点也没有有关系的点，此时可以退出整个dfs了。

经过这次dfs我们得出了所有的答案，有没有觉得很神奇呢？是否对Tarjan算法有更深层次的理解了呢？

#include<iostream>
#include<cstdio>
#include<string.h>
#include<vector>
#define MAN 10005
using namespace std;
vector<int> ve[MAN];
vector<int> pp[MAN];
int fa[MAN],vis[MAN];
int ans,n;
int find(int x)
{
    if(x==fa[x])
    {
        return x;
    }
    else
    {
        return find(fa[x]);
    }
}
void ouin(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y)
    {
        fa[y]=x;
    }
}
void init( )
{
    for(int i=0;i<=n;i++)
    {
        fa[i]=i;
        ve[i].clear();
        pp[i].clear();
        vis[i]=0;
    }
}
void dfs(int u)
{
    vis[u]=1;
    for(int i=0;i<ve[u].size();i++)
    {
        int v=ve[u][i];
        dfs(ve[u][i]);
        ouin(u,ve[u][i]);
    }
    for(int j=0;j<pp[u].size();j++)
    {
        int w=pp[u][j];
        if(vis[w]==1)
        {
            //cout<<w<<endl;
            ans=find(w);
        }
    }
}
int main( )
{
    int t,x,y,a,b;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        init( );
        for(int i=1;i<=n-1;i++)
        {
            scanf("%d%d",&x,&y);
            ve[x].push_back(y);
            vis[y]=1;
        }
        scanf("%d%d",&a,&b);
        pp[a].push_back(b);
        pp[b].push_back(a);
        for(int i=1;i<=n;i++)
        {
            if(vis[i]==0)
            {
                memset(vis,0,sizeof(vis));
                dfs(i);
                break;
            }
        }
        // for(int i=1;i<=n;i++)
        // {
        //  cout<<fa[i]<<" ";
        // }
        cout<<endl;
        printf("%d\n",ans);
    }
    return 0;
}

RMQ与LCA

参考大佬传送门https://www.cnblogs.com/scau20110726/archive/2013/05/26/3100812.html
首先阐述一下RMQ怎么能和LCA扯上关系呢？现在思考一下，最近公共祖先求的是两点的最近的公共祖先。而祖先肯定是在两者上面的，那这么说，祖先的深度是小的。那这样就可以将RMQ与最近公共祖先联系起来了。但是要怎样遍历一棵树才可以将它的深度分清楚呢。
先来操作一波

上面是什么遍历呢。可以看出它是先根，再左再右。这样能保证根一定在前面被遍历。那这样的话根的深度就比子节点小了。
还要注意，这个遍历的特点哦！有回溯的过程哦！保证根节点都在两者之间。
分清遍历序号和节点序号(如图中的A，B......)哦!

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
const int M=20010;
int n;
int head[M],cnt=0;
int vis[M],tot;//tot遍历的序号
int depth[M],tra[M];//depth数组记录每次遍历的深度，tra数组记录的是遍历的节点序号
int dp[M][25];//从第i个连续的2^j深度小的遍历序号
int first[M];//记录每个节点序号第一次出现的遍历序号
struct node
{
    int v,nxt;
}edge[M];
void add(int x,int y)
{
    edge[++cnt].nxt=head[x];
    edge[cnt].v=y;
    head[x]=cnt;
}
void dfs(int x,int deth)
{
    vis[x]=1;
    tra[++tot]=x;//记录节点序号
    depth[tot]=deth;//记录每次遍历序号对应的深度
    first[x]=tot;//记录节点序号第一次出现的遍历序号tot
    for(int i=head[x];i!=-1;i=edge[i].nxt)
    {
        int u=edge[i].v;
        if(!vis[u])
        {
            dfs(u,deth+1);
            tra[++tot]=x;//遍历回溯
            depth[tot]=deth;//每个遍历序号的深度
        }
    }
}
int find(int x,int y)
{
    if(depth[x]<depth[y])//深度小的，返回遍历序号
    {
        return x;
    }
    else
    {
        return y;
    }
    
}
void ST(int n)
{
    for(int i=1;i<=n;i++)
    {
        dp[i][0]=i;
    }
    for(int j=1;j<=24;j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
        {
            dp[i][j]=find(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
        }
    }
}
int RMQ(int i,int j)
{
    int k=log2(j-i+1.0);
    return find(dp[i][k],dp[j-(1<<k)+1][k]);
}
int LCA(int u,int v)
{
    int x=first[u];
    int y=first[v];
    if(x>y)
    {
        swap(x,y);
    }
    int res=RMQ(x,y);//得到了深度最小的遍历序号了
    return tra[res];//返回节点序号
}
int main( )
{
    int t,n,x,y;
    cin>>t;
    while(t--)
    {
        tot=cnt=0;
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        cin>>n;
        for(int i=1;i<n;i++)
        {
            cin>>x>>y;
            add(x,y);
            vis[y]=1;
        }
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])//寻找根节点开始遍历
            {
                memset(vis,0,sizeof(vis));
                dfs(i,1);
                //cout<<i<<" i "<<endl;
                break;
            }
        }
        ST(2*n-1);
        // for(int i=1;i<=2*n-1;i++)
        // {
        //     cout<<tra[i]<<" ";
        // }
        //cout<<endl;
        cin>>x>>y;
        cout<<LCA(x,y)<<endl;
    }
    return 0;
}

倍增

倍增中的ST函数的意思是：在ST算法中，我们维护了一个数组 $DP[i][j]$ ，表示的是以下标为i为起点的长度为 $2^j$ 的序列的信息。然后用动态规划的思想求出整个数组。刚才在上面说我们求LCA时一次要跳2的幂次方层，这就与DP数组中下标 $j$ 的定义不谋而合了。所以我们定义倍增法中的 $DP[i][j]$ 存放的是：结点 $i$ 的向上 $2^j$ 层的祖先。例如下面这个图：

$DP[4][1]=1$ ；结点4的向上 $2^1=2$ 层的祖先是结点1。
$DP[10][1]=2$ ；结点10的向上 $2^1=2$ 层的祖先是结点2。
特别地， $DP[6][0]=3$ ，结点6的向上 $2^0=1$ 层的祖先是3，即6的父节点。而这一现象正好可以当做DP的初始条件。 $DP[i][0]$ 为 $i$ 的父节点。下面写出递推式：
$DP[i][j] = DP[ DP[i][j-1] ] [j-1]$ ，如何理解这个递推式呢？ $DP[i][j-1]$ 是结点i往上跳 $2^{(j-1)}$ 层的祖先，那我们就在跳到这个结点的基础上，再向上跳 $2^{(j-1)}$ 层，这样就相当于从结点i，先跳 $2^{(j-1)}$ 层，跳到 $DP[i][j-1]$ 得到 $2^{(j-1)}$ 祖先节点 $x$ ,节点 $x$ （ $DP[i][j-1]$ ）再跳 $2^{(j-1)}$ 层，最后还是到达了 $2^j$ 层
$DP[10][1]=DP[DP[10][1-1]][1-1]--->DP[5][0]-->2$ , $DP[10][0]$ 表示的是节点10跳1层到节点5，节点5在跳一层就不是节点10跳了2层了。。。。。

再看这副图：
$DP[15][0]=9;DP[15][1]=5;DP[15][2]=2;$
$DP[5][0]=4;DP[5][1]=2;$
$DP[15][2]=DP[DP[15][1]][1]=2$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int deth[11000];
int dp[11000][25];
int vis[11000];
int head[11000];
int cnt;
struct node
{
    int v,nxt;
}edge[11000];
void add(int x,int y)
{
    edge[++cnt].nxt=head[x];
    edge[cnt].v=y;
    head[x]=cnt;
}
void dfs(int x,int u,int dep)
{
    dp[x][0]=u;
    deth[x]=dep;
    for(int i=head[x];i!=-1;i=edge[i].nxt)
    {
        int v=edge[i].v;
        dfs(v,x,dep+1);
    }
}
void Mul(int n)
{
    for(int j=1;(1<<j)<=n;j++)
    {
        for(int i=1;i<=n;i++)
        {
            dp[i][j]=dp[dp[i][j-1]][j-1];
        }
    }
}
int LCA(int x,int y)
{
    if(deth[x]<deth[y])//保证x的深度大
    {
        swap(x,y);
    }
    for(int i=24;i>=0;i--)
    {
        if(deth[x]-(1<<i)>=deth[y])//保证x的深度小于等于y，否则可能把最近公共祖先跳过了
        {
            x=dp[x][i];
        }
    }
    if(x==y)//两者其中之一是对方的祖先
    {
        return x;
    }
    for(int i=24;i>=0;i--)//处于相同层，于是一直往上跳
    {
        if(dp[x][i]!=dp[y][i])//处于相同层，于是一直往上往下跳,直到两者祖先不相同，开始分支x与y再向上跳
                             //如图中的节点9与节点10，直到i=0时两者才不相同，于是x=5,y=6，再返回x节点的1层祖先。图中的节点9与节点14，i=2时祖先相同，但是i=1后面的不相同,于是x=4,y=7;i=0,但是4的1层祖先是2，7的1层祖先是3，所以x=2,y=3;返回节点2的1层祖先
        {
            x=dp[x][i];
            y=dp[y][i];
        }
    }
    return dp[x][0];//dp[y][0]
}
int main( )
{
    int t,n,x,y;
    cin>>t;
    while(t--)
    {
        cin>>n;
        cnt=0;
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        for(int i=1;i<n;i++)
        {
            cin>>x>>y;
            add(x,y);
            vis[y]=1;
        }
        for(int i=1;i<=n;i++)
        {
            if(vis[i]==0)
            {
                //cout<<i<<endl;
                dfs(i,-1,0);
                break;
            }
        }
        Mul(n);
        cin>>x>>y;
        cout<<LCA(x,y)<<endl;
    }
    return 0;
}

最后编辑于：2019.09.27 00:45:54

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 214,377评论 6赞 496
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 91,390评论 3赞 389
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 159,967评论 0赞 349
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,344评论 1赞 288
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,441评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,492评论 1赞 292
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,497评论 3赞 412
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,274评论 0赞 269
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,732评论 1赞 307
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,008评论 2赞 328
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,184评论 1赞 342
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,837评论 4赞 337
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,520评论 3赞 322
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,156评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,407评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,056评论 2赞 365
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,074评论 2赞 352

最近公共祖先(LCA-tarjan/RMQ/倍增)

tarjan求LCA原理：

RMQ与LCA

倍增

推荐阅读更多精彩内容