美文网首页
LCA_最近公共祖先

LCA_最近公共祖先

作者: Gitfan | 来源:发表于2017-08-11 23:18 被阅读0次

　　LCA 最近公共祖先
　　在一棵没有环的树上，每个节点肯定有其父亲节点和祖先节点，而最近公共祖先，就是两个节点在这棵树上深度最大的公共的祖先节点。
　　换句话说，就是两个点在这棵树上距离最近的公共祖先节点。
　　对于一棵有权树，假设u,v两点的最近公共祖先lca(v),若dis[u]表示根节点到u的长度， 则uv间的距离为dis=dis[u]+dis[v]-2*dis[lca(v)]
有人可能会问：那他本身或者其父亲节点是否可以作为祖先节点呢？
　　　　答案是肯定的，很简单，按照人的亲戚观念来说，你的父亲也是你的祖先，而LCA还可以将自己视为祖先节点。
　　　　举个例子吧，如下图所示４和５的最近公共祖先是２，５和３的最近公共祖先是１，２和１的最近公共祖先是１。　

求LCA主要有两种方法:离线的DFS+并查集和在线的RMQ算法
　　这里简单说一说在线和离线的区别:在计算机科学中，一个在线算法是指它可以以序列化的方式一个个的处理输入，也就是说在开始时并不需要已经知道所有的输入。相对的，对于一个离线算法，在开始时就需要知道问题的所有输入数据，而且在解决一个问题后就要立即输出结果。

( 一 )离线算法:tarjan和并查集

Code From Wikipedia

 function TarjanOLCA(u)
     u.ancestor := u;
     for each v in u.children do
         TarjanOLCA(v);
         Union(u,v);
         Find(u).ancestor := u;
     u.color := black;
     for each v such that {u,v} in P do
         if v.color == black
             print "Tarjan's Lowest Common Ancestor of " + u +
                   " and " + v + " is " + Find(v).ancestor + ".";

其中,根节点是可以随意选择的

How far away ？
题意:
给定一棵带权树，求u，v两节点的路径长度
题解：
找到u,v两点的最近公共祖先lca(v)
若dis[u]表示根节点到u的长度，则dis=dis[u]+dis[v]-2*dis[lca(v)]

#include<cstdio>
#include <algorithm>
#include<cstring>
using namespace std;
const int MAXN=40010;
const int BLACK=1,WHITE=0;
int father[MAXN],vis[MAXN],dis[MAXN],color[MAXN];
int parent(int u)
{
    while(u!=father[u])
    {
        father[u]=father[father[u]];
        u=father[u];
    }
    return u;
}
void connect(int u,int v)//v作为u的儿子
{
    int fu=parent(u);
    int fv=parent(v);
    father[fv]=fu;
}
struct Node
{
    int to,next,val;
};
Node edge[MAXN<<1];
int head[MAXN],cnt;
void addEdge(int u,int v,int val)
{
    edge[cnt].to=v;
    edge[cnt].val=val;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].to=u;
    edge[cnt].val=val;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}
struct Ask
{
    int u,to,next,lca;
};
Ask arr[MAXN<<1];
int ask_head[MAXN],idx;
void addAsk(int u,int v)
{
    arr[idx].u=u;arr[idx].to=v;arr[idx].next=ask_head[u];ask_head[u]=idx++;
    arr[idx].u=v;arr[idx].to=u;arr[idx].next=ask_head[v];ask_head[v]=idx++;
}
void tarjan(int u)
{
    vis[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(vis[v]==0)
        {
            dis[v]=dis[u]+edge[i].val;
            tarjan(v);
            connect(u,v);
        }
    }
    color[u]=BLACK;
    for(int i=ask_head[u];i!=-1;i=arr[i].next)
    {
        int v=arr[i].to;
        if(color[v]==BLACK)
        {
            int fa=parent(v);
            arr[i].lca=fa;
            arr[i^1].lca=fa;
        }
    }
}
int main()
{
    int t,n,m,u,v,val;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(head,-1,sizeof(head));
        memset(ask_head,-1,sizeof(ask_head));
        memset(vis,0,sizeof(vis));
        memset(color,WHITE,sizeof(color));
        for(int i=1;i<=n;i++) father[i]=i;
        cnt=idx=0;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            addEdge(u,v,val);
        }
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&u,&v);
            addAsk(u,v);
        }
        dis[1]=0;
        tarjan(1);
        for(int i=0;i<idx;i+=2)
        {
            printf("%d\n",dis[arr[i].u]+dis[arr[i].to]-2*dis[arr[i].lca]);
        }
    }
}

( 二 )在线算法: RMQ算法
一：LCA和RMQ是可以相互转化的
LCA转RMQ算法是一个在线算法：先用时间去做预处理，然后每读入一个询问，就用很短的时间去回答它，即”问一个答一个，回答时间很短“
预备知识：LCA转为RMQ后，几乎是裸的RMQ问题，RMQ问题，这里推荐ST算法求解，如果不懂ST算法，先学习一下



RMQ算法求LCA的模板如下:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=500010;
const int MAXE=500010;
struct Node
{
    int to,next,val;
};
Node edge[MAXE];
int head[MAXN],cnt;
void addEdge(int u,int v,int val)
{
    edge[cnt].to=v;
    edge[cnt].val=val;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
int sequence[MAXN*2];//保存遍历的节点序列,长度为2*n-1,从下标1开始保存
int deep[MAXN*2];//和遍历序列对应的深度数组,长度为2*n-1,从下标1开始保存
int first[MAXN];//每个节点在遍历序列时第一次出现的位置
int dis[MAXN];//每个节点到树根的距离
int dp[MAXN*1][25];//Sparse_table
bool vis[MAXN];//DFS遍历的访问数组
int tot;//序列下标记录
void DFS(int u,int dep)
{
    vis[u]=1;
    sequence[++tot]=u;first[u]=tot;deep[tot]=dep;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(vis[v]==0)
        {
            dis[v]=dis[u]+edge[i].val;
            DFS(v,dep+1);
            sequence[++tot]=u;
            deep[tot]=dep;
        }
    }
}
void ST(int len)//index from 1 - len
{
    for(int i=1;i<=len;i++) dp[i][0]=i;

    for(int j=1;(1<<j)<=len;j++)//(length)=j<<1
        for(int i=1;i+(1<<j)-1<=len;i++)
        {
            int a=dp[i][j-1],b=dp[i+(1<<(j-1))][j-1];
            if(deep[a]<deep[b]) dp[i][j]=a;
            else dp[i][j]=b;
        }
}
int RMQ(int x,int y)
{
    int k=0;
    while(1<<(k+1)<=y-x+1) k++;
    int a=dp[x][k],b=dp[y-(1<<k)+1][k];
    if(deep[a]<deep[b]) return a;
    else return b;
}
int LCA(int a,int b)
{
    int x=first[a],y=first[b];
    if(x>y) swap(x,y);
    return sequence[RMQ(x,y)];
}
int main()
{
    int t,n,m,u,v,val;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        cnt=tot=0;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            addEdge(u,v,val);
            addEdge(v,u,val);
        }
        dis[1]=0;
        DFS(1,1);
        ST(tot);
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&u,&v);
            printf("%d\n",dis[u]+dis[v]-2*dis[LCA(u,v)]);
        }
    }
}

类似的,这里给出带有pos数组的RMQ算法

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=40010;
const int MAXE=MAXN*2;
struct Node
{
    int to,next,val;
};
Node edge[MAXE];
int head[MAXN],cnt;
void addEdge(int u,int v,int val)
{
    edge[cnt].to=v;
    edge[cnt].val=val;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
int sequence[MAXN*2];//保存遍历的节点序列,长度为2*n-1,从下标1开始保存
int deep[MAXN*2];//和遍历序列对应的深度数组,长度为2*n-1,从下标1开始保存
int first[MAXN];//每个节点在遍历序列时第一次出现的位置
int dis[MAXN];//每个节点到树根的距离
int dp[MAXN*2][25];//Sparse_table
int pos[MAXN*2][25];
bool vis[MAXN];//DFS遍历的访问数组
int tot;//序列下标记录
int temp[MAXN*2];
void DFS(int u,int dep)
{
    vis[u]=1;
    sequence[++tot]=u;first[u]=tot;deep[tot]=dep;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(vis[v]==0)
        {
            dis[v]=dis[u]+edge[i].val;
            DFS(v,dep+1);
            sequence[++tot]=u;
            deep[tot]=dep;
        }
    }
}
void ST(int len)//index from 1 - len
{
    for(int i=1;i<=len;i++) dp[i][0]=deep[i];
    for(int i=1;i<=len;i++) pos[i][0]=i;

    for(int j=1;(1<<j)<=len;j++)//(length)=j<<1
        for(int i=1;i+(1<<j)-1<=len;i++)
        {
            if(dp[i][j-1]<dp[i+(1<<(j-1))][j-1])
            {
                dp[i][j]=dp[i][j-1];
                pos[i][j]=pos[i][j-1];
            }
            else
            {
                dp[i][j]=dp[i+(1<<(j-1))][j-1];
                pos[i][j]=pos[i+(1<<(j-1))][j-1];
            }
        }
}
int RMQ(int x,int y)
{
    int k=0;
    while(1<<(k+1)<=y-x+1) k++;
    return dp[x][k]<dp[y-(1<<k)+1][k]?pos[x][k]:pos[y-(1<<k)+1][k];
}
int LCA(int a,int b)
{
    int x=first[a],y=first[b];
    if(x>y) swap(x,y);
    return sequence[RMQ(x,y)];
}
int main()
{
    int t,n,m,u,v,val;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        cnt=tot=0;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            addEdge(u,v,val);
            addEdge(v,u,val);
        }
        dis[1]=0;
        DFS(1,1);
        ST(tot);
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&u,&v);
            printf("%d\n",dis[u]+dis[v]-2*dis[LCA(u,v)]);
        }
    }
}

Design the city
题意:
求树的三点距离
题解:
u,v,w三点距离其实等于(dis(u,v)+dis(u,w)+dis(v,w))/2;
方法一:离线算法:tarjan和并查集

#include<cstdio>
#include <algorithm>
#include<cstring>
using namespace std;
const int MAXN=50010;
const int BLACK=1,WHITE=0;
int father[MAXN],vis[MAXN],dis[MAXN],color[MAXN];
int parent(int u)
{
    while(u!=father[u])
    {
        father[u]=father[father[u]];
        u=father[u];
    }
    return u;
}
void connect(int u,int v)//v作为u的儿子
{
    int fu=parent(u);
    int fv=parent(v);
    father[fv]=fu;
}
struct Node
{
    int to,next,val;
};
Node edge[MAXN<<1];
int head[MAXN],cnt;
void addEdge(int u,int v,int val)
{
    edge[cnt].to=v;
    edge[cnt].val=val;
    edge[cnt].next=head[u];
    head[u]=cnt++;
    edge[cnt].to=u;
    edge[cnt].val=val;
    edge[cnt].next=head[v];
    head[v]=cnt++;
}
struct Ask
{
    int u,to,next,lca;
};
Ask arr[70010*6];
int ask_head[MAXN],idx;
void addAsk(int u,int v)
{
    arr[idx].u=u;arr[idx].to=v;arr[idx].next=ask_head[u];ask_head[u]=idx++;
    arr[idx].u=v;arr[idx].to=u;arr[idx].next=ask_head[v];ask_head[v]=idx++;
}
void tarjan(int u)
{
    vis[u]=1;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(vis[v]==0)
        {
            dis[v]=dis[u]+edge[i].val;
            tarjan(v);
            connect(u,v);
        }
    }
    color[u]=BLACK;
    for(int i=ask_head[u];i!=-1;i=arr[i].next)
    {
        int v=arr[i].to;
        if(color[v]==BLACK)
        {
            int fa=parent(v);
            arr[i].lca=fa;
            arr[i^1].lca=fa;
        }
    }
}
int main()
{
    int t,n,m,u,v,w,val,cas=0;
    while(scanf("%d",&n)!=EOF)
    {
        if(cas++) printf("\n");
        memset(head,-1,sizeof(head));
        memset(ask_head,-1,sizeof(ask_head));
        memset(vis,0,sizeof(vis));
        memset(color,WHITE,sizeof(color));
        for(int i=1;i<=n;i++) father[i]=i;
        cnt=idx=0;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            addEdge(u+1,v+1,val);
        }
        scanf("%d",&m);
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            addAsk(u+1,v+1);addAsk(u+1,w+1);addAsk(v+1,w+1);
        }
        dis[1]=0;
        tarjan(1);
        for(int i=0;i<idx;i+=6)
        {
            int d1=dis[arr[i].u]+dis[arr[i].to]-2*dis[arr[i].lca];
            int d2=dis[arr[i+2].u]+dis[arr[i+2].to]-2*dis[arr[i+2].lca];
            int d3=dis[arr[i+4].u]+dis[arr[i+4].to]-2*dis[arr[i+4].lca];
            printf("%d\n",(d1+d2+d3)/2);
        }
    }
}

方法二:在线算法: RMQ算法

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=50010;
const int MAXE=MAXN*2;
struct Node
{
    int to,next,val;
};
Node edge[MAXE];
int head[MAXN],cnt;
void addEdge(int u,int v,int val)
{
    edge[cnt].to=v;
    edge[cnt].val=val;
    edge[cnt].next=head[u];
    head[u]=cnt++;
}
int first[MAXN];
int vis[MAXN];
int deep[MAXN*2];
int sequence[MAXN*20];
int dis[MAXN];
int dp[MAXN*2][25];
int tot;
void DFS(int u,int dep)
{
    vis[u]=1;
    sequence[++tot]=u;deep[tot]=dep;first[u]=tot;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(vis[v]==0)
        {
            dis[v]=dis[u]+edge[i].val;
            DFS(v,dep+1);
            sequence[++tot]=u;
            deep[tot]=dep;
        }
    }
}
void ST(int len)
{
    for(int i=1;i<=len;i++) dp[i][0]=i;
    for(int j=1;(1<<j)<=len;j++)
    {
        for(int i=1;i+(1<<j)-1<=len;i++)
        {
            int a=dp[i][j-1],b=dp[i+(1<<(j-1))][j-1];
            if(deep[a]<deep[b]) dp[i][j]=dp[i][j-1];
            else dp[i][j]=dp[i+(1<<(j-1))][j-1];
        }
    }
}
int RMQ(int x,int y)
{
    int k=0;
    while((1<<(k+1))<=y-x+1) k++;
    return deep[dp[x][k]]<deep[dp[y-(1<<k)+1][k]]?dp[x][k]:dp[y-(1<<k)+1][k];
}
int LCA(int u,int v)
{
    int x=first[u],y=first[v];
    if(x>y) swap(x,y);
    return sequence[RMQ(x,y)];
}
int main()
{
    int n,m,u,v,val,a,b,c;
    bool start=true;
    while(scanf("%d",&n)!=EOF)
    {
        if(!start) printf("\n");
        memset(head,-1,sizeof(head));
        memset(vis,0,sizeof(vis));
        cnt=tot=0;
        for(int i=1;i<n;i++)
        {
            scanf("%d%d%d",&u,&v,&val);
            addEdge(u+1,v+1,val);
            addEdge(v+1,u+1,val);
        }
        dis[1]=0;
        DFS(1,1);
        ST(tot);
        scanf("%d",&m);
        while(m--)
        {
            scanf("%d%d%d",&a,&b,&c);
            a++;b++;c++;
            int d1=dis[a]+dis[b]-2*dis[LCA(a,b)];
            int d2=dis[a]+dis[c]-2*dis[LCA(a,c)];
            int d3=dis[b]+dis[c]-2*dis[LCA(b,c)];
            printf("%d\n",(d1+d2+d3)/2);
        }
        start=false;
    }
}

题目推荐:
CODEVS 2370 小机房的树
CODEVS 1036 商务旅行
METO CODE 223 拉力赛
HDU 2586 How far way?
ZOJ 3195 Design the city

相关文章

  • LCA_最近公共祖先

    LCA 最近公共祖先在一棵没有环的树上，每个节点肯定有其父亲节点和祖先节点，而最近公共祖先，就是两个节点在这棵树上...

  • 最近公共祖先

    LeetCode题目地址 在root为根的二叉树中找A,B的LCA: 如果找到了就返回这个LCA 如果只碰到A，就...

  • 最近公共祖先

    最近公共祖先 简称LCA（Lowest Common Ancestor），所谓LCA，是当给定一个有根树T时，对于...

  • 最近公共祖先

    https://www.lintcode.com/problem/lowest-common-ancestor-o...

  • 最近公共祖先系列

    最近公共祖先I 描述： 给定一棵二叉树，找到两个节点的最近公共父节点 (LCA)。最近公共祖先是两个节点的公共的祖...

  • lintcode 最近公共祖先

    给定一棵二叉树，找到两个节点的最近公共父节点(LCA)。最近公共祖先是两个节点的公共的祖先节点且具有最大深度。样例...

  • LCA问题及其倍增解法

    [TOC] LCA，最近公共祖先 在有根树中，找出某两个结点u和v最近的公共祖先（或者说，离树根最远的公共祖先）。...

  • LCA（最近公共祖先）算法

    在一棵没有环的树上，每个节点肯定有其父亲节点和祖先节点，而最近公共祖先，就是两个节点在这棵树上深度最大的公共的祖先...

  • 算法—— 最近公共祖先 III

    给一棵二叉树和二叉树中的两个节点，找到这两个节点的最近公共祖先LCA。两个节点的最近公共祖先，是指两个节点的所有父...

  • 二叉树-最近的公共祖先

    已知二叉树，求二叉树中给定的两个节点的最近公共祖先。 最近公共祖先: 两节点v与w的最近公共祖先u，满足在树上最低...

网友评论

      本文标题：LCA_最近公共祖先

      本文链接：https://www.haomeiwen.com/subject/knzrrxtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|LCA_最近公共祖先|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！