树上倍增求LCA（最近公共祖先）

时间：2021-07-19 16:47:14
    前几天做faebdc学长出的模拟题，第三题最后要倍增来优化，在学长的讲解下，尝试的学习和编了一下倍增求LCA（我能说我其他方法也大会吗？。。）

倍增求LCA：

father【i】【j】表示节点i往上跳2^j次后的节点

可以转移为

father【i】【j】=father【father【i】【j-1】】【j-1】

（此处注意循环时先循环j，再循环i）

然后dfs求出各个点的深度depth

整体思路：

先比较两个点的深度，如果深度不同，先让深的点往上跳，浅的先不动，等两个点深度一样时，if 相同 直接返回，if 不同 进行下一步；如果不同，两个点一起跳，j从大到小枚举（其实并不大），如果两个点都跳这么多后，得到的点相等，两个点都不动（因为有可能正好是LCA也有可能在LCA上方），知道得到的点不同，就可以跳上来，然后不断跳，两个点都在LCA下面那层，所以再跳1步即可，当father【i】【j】中j=0时即可，就是LCA，返回值结束

感谢Sunshinezff学长的编码纠错帮助

下面是代码：“`

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<queue>

using namespace std;

vector <int> g[100010];

int father[100010][40]={0};

int depth[100010]={0};

int n,m;

bool visit[10010]={false};

int root;

void dfs(int u)

{

    int i;

    visit[u]=true;

    for (i=0;i<g[u].size();i++)

        {

            int v=g[u][i];

            if ( !visit[v] )

             {

                    depth[v]=depth[u]+1;

                    dfs(v);

             }

        }

}//深搜出各点的深度，存在depth中 

void bz()

{

    int i,j;

    for (j=1;j<=30;j++)

        for (i=1;i<=n;i++)

            father[i][j]=father[father[i][j-1]][j-1];

}//倍增，处理father数组，详情参照上述讲解 

int LCA(int u,int v)

{

    if ( depth[u]<depth[v] )

    {

        int temp=u;

        u=v;

        v=temp;

    }//保证深度大的点为u，方便操作

    int dc=depth[u]-depth[v];

    int i;

    for (i=0;i<30;i++)//值得注意的是，这里需要从零枚举

    {

        if ( (1<<i) & dc)//一个判断，模拟一下就会很清晰

         u=father[u][i];

    }

    //上述操作先处理较深的结点，使两点深度一致

    if (u==v) return u;//如果深度一样时，两个点相同，直接返回

    for (i=29;i>=0;i--)

    {

        if (father[u][i]!=father[v][i])//跳2^j步不一样，就跳，否则不跳

        {

            u=father[u][i];

            v=father[v][i];

        }

    }

    u=father[u][0];//上述过程做完，两点都在LCA下一层，所以走一步即可

    return u;

}

int main()

{

    int i,j;

    scanf("%d",&n);

    for (i=0;i<=n;i++)

     g[i].clear();

     for (i=1;i<n;i++)

        {

            int a,b;

            int root;

            scanf("%d%d",&a,&b);

            g[a].push_back(b);

            father[b][0]=a;

            if (father[a][0]==0)

                root=a;

        }

    depth[root]=1;

    dfs(root);

    bz();

    int x,y;

    scanf("%d%d",&x,&y);

    printf("%d",LCA(x,y));

  return 0;

}

“`

相关文章