倍增实现LCA

Today，we will talk about how to find The Least Common Ancestor.

Now ,let us get into the business（正题）.

为了大家可以更好地理解......

I will use chinese. 好吧，我装不下去了.

写在前面：

会有人问，不写最简单的暴力，一开始就写倍增实现，会不会有点太唐突。
我想说，其实二者思路几乎一致，后者只是前者稍微修改一下而已。明白
了倍增，暴力几乎对着打。

开始对LCA的讲解：

　　LCA是啥？吃？，LCA表示在树上两点之间的最近公共祖先。

　　以下图为例，手工画作可能会比较粗糙，凑合着看吧。

2 和 3的 LCA 是多少呢 ? 显然他们只有 1 一个祖先，所以1 没毛病。

那么 5 和 8 的 LCA是是多少呢？ 8->4->2 , 5->2, 所以他的们的 LCA是 4.

那么如何实现LCA呢？

首先定义几个数组：

　　deep[ i ]数组表示第 i 个节点所在的深度层数。

　　up[ i ][ j ] , 注意是个二维数组，表示第 i 个节点向上 2^j 层所到达的节点，，例如上图p[13][1]=4。

　　dis[ i ][ j ]，也是二维哦，表示从第 i 个点向上 2^j 层上的那个点的权值(也就是距离)，若权值都唯一，可忽略。

当然你还需要连边建树：

　　这就不多bb了。

int head[maxn],tot;
void add(int x,int y)
{
    edge[++tot].nxt=head[x],edge[tot].to=y;head[x]=tot;　　// 注意一下双向边
}

开始分析：

　　deep[ ]数组：

　　　　deep[x]=deep[ fa[x] ]+1,fa[x]表示x的父节点，这点很显然，没啥好说的。 

　　up[ ][ ]数组 ：

　　　　这个数组比较有意思，确切的说是 关于2的乘方 比较好玩了。

　　　　up[ x ][ i ] = up[ up[ x ][ i-1 ] ][i-1] (颜色区分下),

　　　　你可以理解为 2ⁱ = 2^i-1 + 2^i-1 。

　　　　有问题？那么我们可以一步一步探讨一下。

　　　　先看标记部分先跳到x向上 2^i-1 个点，记为u点，那么再从u点向上 2^j-1 层，则相对于x点来说不就可以看作 向上2 * 2^i-1 =2ⁱ 层么。

　　　　还不理解的话，可以从图上手动演示下。

　　dis[ ][ ]数组：

　　　　dis[ i ][ j ] = dis[ i ][ j-1 ] + dis[ up[ i ][ j-1 ] ][ j-1 ].

　　　　若已经明白以上 up 数组 则明白这个性质了，在这不不做过多解释(不明白？按照上图手演)。

开始dfs预处理部分：

　　通过对以上数组的解释这部分几乎已经讲解完了。

　　看代码，可能会更好的帮你理解：

void dfs(int u,int fa)        // u表示当前节点，fa表示其父节点。 
{
    deep[u]=deep[fa]+1; p[u][0]=fa;        //这行没啥问题。 
    for(int i=1;(1<<i)<=deep[u];i++)p[u][i]=p[p[u][i-1]][i-1];    //深度跳跃，上边有解释。 
    for(int i=head[u];i;i=edge[i].nxt)
        if(edge[i].to!=fa)dfs(edge[i].to,u);    // if判断是否是节点的爸爸，因为他们之间有边啊 
}

那么开始实现LCA了吧：

　　1.首先我们需要判断一下谁深谁浅，记所求LCA的两点位a，b。

　　这简单，

if(deep[a]>deep[b])swap(a,b);

　　确保a比b浅，也就是在树上，a点相比较于b点较高。

　　2.将两点转化为在同一深度。

　　那么a点比较高，那么就从b点开始往上跳吧。

　　先代码，后解释。

for(int i=20;i>=0;i--)
    if(deep[a]<=deep[b]-(1<<i))b=p[b][i];

　　注意这时候向上跳的i我们需要从大数开始枚举，20的话足够大了，想..2²⁰多少层了。

　　我们不允许b点跳的比a高，若b点向上跳，跳不超，那么就让b向上跳。

　　这里还是 2的乘方 的性质，循环过后，他两个一定在同一层(why? 小于2ⁱ的数绝对可以用x(x<i),相加得到 )。

　　3.特判一下(避免浪费时间)

　　if(a==b)return a;

　　4.一起往上跳

　　for(int i=20;i>=0;i--)
    {
        if(p[a][i]==p[b][i])continue;
        else a=p[a][i],b=p[b][i];
    }

　　跳完以后他们就在同一深度，并且a和b任意一个节点的父节点，为a和b的公共祖先，都是父节点了，当然是最近的咯。

这一部分代码：

int lca(int a,int b)
{
    if(deep[a]>deep[b])swap(a,b);
    for(int i=20;i>=0;i--)
    if(deep[a]<=deep[b]-(1<<i))b=p[b][i];
    if(a==b)return a;
    for(int i=20;i>=0;i--)
    {
        if(p[a][i]==p[b][i])continue;
        else a=p[a][i],b=p[b][i];
    }
    return p[a][0];
}

　　

luogu P3379 【模板】最近公共祖先（LCA）

代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#define maxn int(5e5+2)
using namespace std;
struct ahah{
    int nxt,to;
}edge[maxn];
int n,m,s;
int head[maxn],tot;
void add(int x,int y)
{
    edge[++tot].nxt=head[x],edge[tot].to=y;head[x]=tot;
}
int deep[maxn],p[maxn][22];
void dfs(int u,int fa)        // u表示当前节点，fa表示其父节点。 
{
    deep[u]=deep[fa]+1; p[u][0]=fa;        //这行没啥问题。 
    for(int i=1;(1<<i)<=deep[u];i++)p[u][i]=p[p[u][i-1]][i-1];    //深度跳跃，上边有解释。 
    for(int i=head[u];i;i=edge[i].nxt)
        if(edge[i].to!=fa)dfs(edge[i].to,u);    // if判断是否是节点的爸爸，因为他们之间有边啊 
}
int lca(int a,int b)
{
    if(deep[a]>deep[b])swap(a,b);
    for(int i=20;i>=0;i--)
    if(deep[a]<=deep[b]-(1<<i))b=p[b][i];
    if(a==b)return a;
    for(int i=20;i>=0;i--)
    {
        if(p[a][i]==p[b][i])continue;
        else a=p[a][i],b=p[b][i];
    }
    return p[a][0];
}
int main()
{
    int a,b;
    scanf("%d%d%d",&n,&m,&s);
    for(int i=1;i<n;i++)scanf("%d%d",&a,&b),add(a,b),add(b,a);
    dfs(s,0);
    while(m--)
    {
        scanf("%d%d",&a,&b);
        printf("%d
",lca(a,b));
    }
}

　　

#include<stdio.h>
#include<string.h>
#include<vector>
#include<stdlib.h>
#include<math.h>
#define max 40001
#define maxl 25
using namespace std;
typedef struct
{
    int from,to,w;
}edge;//这个结构体用来存储边
 
vector<edge>edges;
vector<int> G[max];
//保存边的数组
int grand[max][maxl],gw[max][maxl];//x向上跳2^i次方的节点，x到他上面祖先2^i次方的距离
int depth[max];//深度
int n,m,N;
void addedge(int x,int y,int w)//把边保存起来的函数
{
   edge a={x,y,w},b={y,x,w};
   edges.push_back(a);
   edges.push_back(b);
 
   G[x].push_back(edges.size()-2);
   G[y].push_back(edges.size()-1);
}
void dfs(int x)//dfs建图
{
    for(int i=1;i<=N;i++)//第一个几点就全部都是0咯，第二个节点就有变化了，不理解的话建议复制代码输出下这些数组
 
    {
        grand[x][i]=grand[grand[x][i-1]][i-1];
        gw[x][i]=gw[x][i-1]+gw[grand[x][i-1]][i-1];
       // if(grand[x][i]==0) break;
    }
 
    for(int i=0;i<G[x].size();i++)
    {   edge  e = edges[G[x][i]];
         if(e.to!=grand[x][0])//这里我们保存的是双向边所以与他相连的边不是他父亲就是他儿子父亲的话就不能执行，不然就死循环了。
 
           {
                depth[e.to]=depth[x]+1;//他儿子的深度等于他爸爸的加1
                grand[e.to][0]=x;//与x相连那个节点的父亲等于x
                gw[e.to][0]=e.w;//与x相连那个节点的距离等于这条边的距离
                dfs(e.to);//深搜往下面建
           }
    }
}
void Init(){
    //n为节点个数
    N = floor(log(n + 0.0) / log(2.0));//最多能跳的2^i祖先
    depth[1]=0;//根结点的祖先不存在，用-1表示
    memset(grand,0,sizeof(grand));
    memset(gw,0,sizeof(gw));
    dfs(1);//以1为根节点建树
 
}
int lca(int a,int b)
{ if(depth[a] > depth[b]) swap(a, b);//保证a在b上面，便于计算
    int ans = 0;
    for(int i = N; i >= 0; i--) //类似于二进制拆分，从大到小尝试
        if(depth[a] < depth[b] && depth[grand[b][i]] >= depth[a])//a在b下面且b向上跳后不会到a上面
            ans +=gw[b][i], b=grand[b][i];//先把深度较大的b往上跳
 
    for(int j=N;j>=0;j--)//在同一高度了,他们一起向上跳,跳他们不相同节点，当全都跳完之后grand【a】【0】就是lca,上面有解释哈。
    {
        if(grand[a][j]!=grand[b][j])
        {   ans+=gw[a][j];
            ans+=gw[b][j];
            a=grand[a][j];
            b=grand[b][j];
 
        }
    }
    if(a!=b)//a等于b的情况就是上面土色字体的那种情况
    {
        ans+=gw[a][0],ans+=gw[b][0];
    }
    return ans;
}
int main()
{ int t ;
  scanf("%d",&t);
  while(t--)
  {   scanf("%d%d",&n,&m);
      for(int i=1;i<n;i++)
      {
          int x,y,w;
          scanf("%d%d%d",&x,&y,&w);
          addedge(x,y,w);
      }
     Init();
     for(int i=1;i<=m;i++)
     {
         int x,y;
         scanf("%d%d",&x,&y);
         printf("%d
",lca(x,y));
     }
  }
}