LCA_最近公共祖先

　　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;
    }
}

最后编辑于：2017.12.10 01:00:01

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

LCA_最近公共祖先

推荐阅读更多精彩内容