本文正在参加「金石计划」

倍增？最近公共先人？——从定义到实现，帮你一步步吃掉它！

一、倍增倍增——翻倍的增加

倍增是一种思维，实际上的操作便是经过不断翻倍来缩短咱们的处理时刻：

它能够把线性级别的处理优化到指数级。

举个栗子：

现在有8个格子，我想从第1个格子去到第6个格子，怎样做到呢？

最简略的做法便是直接一格一格的走到6号格子里，确实很简略，但这样子处理需求走5个格子。

让咱们来看看倍增是怎样处理的：

其实如此一看，这个倍增就跟二进制相同。

并且咱们在倍增处理的过程中，进行了一种 “擦边球” 行为，即咱们能去到目的地及其它之后的地方，但咱们不去。

这样处理，到了最终咱们就会离目的地无限接近，那么只要再一步，就能够到达目的地了。

事实上，咱们在使用倍增来求最近公共先人时也是相似这样的操作。

倍增的思维其实非常简略，可是重点是该怎样去使用它。

接下来让咱们看看——

二、公共先人——这玩意还能公共吗

开个玩笑，这个所谓先人和咱们平日里说的”祖宗十八代“并不是同一个东西，就像咱们在学习树状结构的时分称号一个子节点的上面连着的节点是父节点相同，先人节点也是相似的意思，不过父亲节点只要一个，而先人节点则能够有很多个。

咱们这儿的公共先人，浅显理解便是：

在同一颗树上，两个不同节点去往根节点时会经过的相同节点。

比方在这棵树中:

节点3去往根节点4的途径是：3->1->4。
节点5去往根节点4的途径是：5->1->4。

那么1和4都是它们经过的节点，咱们就称这两个点是3和5的公共先人。

最近公共先人（LCA）便是离3和5最近的先人节点，即节点1。

又比方2和3的最近公共先人是4。

有些标题还会问两个相同节点的公共先人，比方3和3，那么此刻它们的公共先人便是它们自己。 ~~（？好古怪的说法）~~

到了这儿，公共先人和倍增的理念咱们都了解了，接下来进入咱们的——

三、求先人——喂你咋跪下了

上面一节在介绍公共先人时，咱们是怎样求出那颗树的3和5节点的公共先人的？

咱们是先从节点3走回根节点，然后再从节点5走回根节点，记录这两次的途径，途径上相同的节点便是它们的公共先人，离他们最近的那个便是公共先人了。

这个做法是没有问题的，确实能够求出正确的答案。可是缺陷是太慢了！

咱们看一看这样做的时刻复杂度：

哪怕咱们预处理并记录下一切节点到达根节点的途径，可是咱们每次在问询两个点的最近公共先人时，都要遍历一遍它俩的途径，这样单次问询的最坏复杂度是O(n)。

数据量小还好说，数据量大那是妥妥的死。所以咱们要想办法去优化它。

这儿咱们选用的便是倍增法了。（别忘了咱们的“擦边球”操作）

可是这样做其实有个问题，比方求节点2和节点3的公共先人：

节点2的途径是：2->4；
节点3的途径是：3->1->4;

咱们能够发现，假如此刻咱们一同移动，那么成果会是错误的，由于它们并没有一同相等的途径节点。

这是由于它俩到根节点的途径并不相同长，为了处理这个问题，咱们应该确保节点2和3的剩余途径相同长。

即把节点3先移动到节点1。

为了便利处理这一状况，咱们借用了树状结构中——“深度”的概念，即一个节点到根节点的间隔。

用一个数组deep[]来保护节点的深度，初始设定deep[根节点]=1。
然后经过一遍dfs，在记录途径的一同也处理好每个节点的深度。
当咱们求两个节点的最近公共先人时，假如深度不相同，咱们把深度较大的那个点先往上移动，直到两个节点的深度相等。
假如移动到深度相一同，咱们发现这两个节点相同了，那么就阐明这便是本来节点的最近公共先人。

这便是经过倍增法求解最近公共先人的做法了。

不过还有个之前被咱们忽视的问题：咱们该怎样记录途径？

假如每个节点都开个数组来存途径节点，占空间不说，实际操作起来也很慢。并且咱们能够发现，并不是途径上一切的节点咱们都需求，咱们只需求每个节点的：第2^0个、第2^1个、第2^2个、……、第2^k个先人就行。

这儿咱们还是选用的倍增的思维：

先预备一个先人数组fa[N] [30]，fa[i] [j]表明节点i的第2^(j-1)个先人节点。

比方这样一棵树：

fa[8] [0]=7;
fa[8] [1]=6;
fa[8] [2]=3;
fa[8] [3]=1;

那么该怎样推出这么一个公式呢？

咱们能够发现：

fa[8] [0]其实便是8节点的父节点7。
fa[8] [1]便是7的第2^0个节点。
fa[8] [2]是fa[8] [1]的第2^1个节点。
……以此类推。

咱们能够得到一个状态转移方程：

f a [i] [k] = f a [(f a [i] [k - 1])] [k - 1];

由于咱们是不断核算i节点的第2^（1、2、3、……、k）个节点。能够知道k的上限为：

log_2^{deep[i]}

一般来说k最大不会超过20。

这样咱们就能够快速的记录下每一个点的先人节点了。

至此，倍增思维求最近公共先人的办法咱们现已全部学会了，接下来让咱们——

四、用代码实现

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

//#pragma GCC optimize(2)
//#pragma GCC optimize(3)

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 5e5 + 50, MOD = 998244353;

//用二维数组模拟邻接表来存储树
vector<int>tree[N];
//deep记录每个节点的深度
//fa[i][k]表明节点i的第2^k个先人
int deep[N], fa[N][32];

//dfs一遍求出一切点的深度和先人节点
//x是当前节点，y是它的父节点
void dfs(int x, int y)
{
    //x的第2^0个节点便是父节点
    fa[x][0] = y;
    //逐渐获取上面的先人节点
    for (int i = 1; i < 20; i++)
    {
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
    }
    //遍历和点x链接的点
    for (auto& i : tree[x])
    {
        //防止往上跑，假如遇到的节点是父节点，咱们就不去
        if (i == y)continue;
        子节点的深度是父节点+1
        deep[i] = deep[x] + 1;
        dfs(i, x);
    }
}

//求x和y的最近公共先人
int lca(int x, int y)
{
    //假如两节点深度不相同，咱们把他们移动到同一深度
    if (deep[x] != deep[y])
    {
        //为了不麻烦，咱们都只处理x
        //咱们移动深度大的到上面
        if (deep[x] < deep[y])swap(x, y);
        for (int i = 20; i >= 0; i--)
        {
            //假如跳的点深度仍是大于等于y的，咱们才跳（擦边球操作）
            if (deep[fa[x][i]] >= deep[y])
                x = fa[x][i];
        }
    }
    //假如深度相同了，俩节点相同，阐明这个节点便是本来x和y的最近公共先人
    if (x == y)return x;
    //开端俩边点一同往上跳
    for (int i = 20; i >= 0; i--)
    {
        //获取他俩的第2^i个先人
        int a = fa[x][i], b = fa[y][i];
        //只要不相同了，咱们才跳（擦边球操作）
        if (a != b)
        {
            x = a, y = b;
        }
    }
    //最终，它们的父节点便是最近公共先人
    return fa[x][0];
}

void solve()
{
    int n, m, x, y;
    cin >> n >> m;
    for (int i = 1; i < n; i++)
    {
        cin >> x >> y;
        tree[y].push_back(x);
        tree[x].push_back(y);
    }
    //初始根节点深度设为1
    //注意是根节点，假如标题没说出，咱们默认是1，假如说了，就依照标题说的来
    deep[1] = 1;
    dfs(1, 0);
    while (m--)
    {
        cin >> x >> y;
        cout << lca(x, y) << endl;
    }
}

signed main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cout.tie(nullptr);
   int t = 1;
   // cin >> t;
   while (t--)
   {
     solve();
   }
   return 0;
}

五、给我题！我要试一试！

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

这题便是一个模板题，唯一要注意的是这题的根节点root是给定的，咱们要依照给定的根节点来运算。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

//#pragma GCC optimize(2)
//#pragma GCC optimize(3)

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 5e5 + 50, MOD = 998244353;

vector<int>tree[N];
int deep[N], fa[N][32];

int lca(int x, int y)
{
    if (deep[x] != deep[y])
    {
        if (deep[x] < deep[y])swap(x, y);
        for (int i = 20; i >= 0; i--)
        {
            if (deep[fa[x][i]] >= deep[y])x = fa[x][i];
        }
    }
    if (x == y)return x;
    for (int i = 20; i >= 0; i--)
    {
        int a = fa[x][i], b = fa[y][i];
        if (a != b)
        {
            x = a, y = b;
        }
    }
    return fa[x][0];
}

void dfs(int x, int y)
{
    fa[x][0] = y;
    for (int i = 1; i < 20; i++)
    {
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
    }
    for (auto& i : tree[x])
    {
        if (i == y)continue;
        deep[i] = deep[x] + 1;
        dfs(i, x);
    }
}

void solve()
{
    int n, m, root, x, y;
    cin >> n >> m >> root;
    for (int i = 1; i < n; i++)
    {
        cin >> x >> y;
        tree[y].push_back(x);

        tree[x].push_back(y);
    }
    //依照标题给的根节点来运算
    deep[root] = 1;
    dfs(root, 0);
    while (m--)
    {
        cin >> x >> y;
        cout << lca(x, y) << endl;
    }
}

signed main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cout.tie(nullptr);
   int t = 1;
   // cin >> t;
   while (t--)
   {
     solve();
   }
   return 0;
}

Problem – 2586 (hdu.edu.cn)

这题是让咱们求树中任意两个点之间的间隔。

其实这便是lca非常常见的用法了，比方这么一棵树：

咱们先求出一切点到达根节点的间隔，这步只需求在dfs和深度一同处理。

用一个数组dis记录下来，dis[i]表明节点i到根节点的间隔为dis[i]:

假如咱们想求点x到点y的间隔，只需求求得他俩的最近公共先人z，此刻x和y的间隔是：

l e n = d i s [x] + d i s [y] - 2 * d i s [z];

比方咱们想求2和6的间隔，能够发现转折点在3，也便是他俩的公共先人。

那么点2到点3的间隔就为：dis[2]-dis[3]；
再求点6到点3的间隔就为：dis[6]-dis[3]；
那么点2的间隔到点6的间隔就为：dis[2]+dis[6]-dis[3]-dis[3];

只要咱们知道这两点的最近公共先人，咱们就能够很快的求出这两点的间隔了。

AC代码

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<math.h>
#include<set>
#include <random>
#include<numeric>
#include<string>
#include<string.h>
#include<iterator>
#include<fstream>
#include<map>
#include<unordered_map>
#include<stack>
#include<list>
#include<queue>
#include<iomanip>
#include<bitset>

//#pragma GCC optimize(2)
//#pragma GCC optimize(3)

#define endl '\n'
#define int ll
#define PI acos(-1)
#define INF 0x3f3f3f3f
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll>PII;
const int N = 5e5 + 50, MOD = 998244353;

vector<int>tree[N];
int deep[N], fa[N][32], dis[N];
//存储的是边权
unordered_map<int, unordered_map<int, int>>mymap;

int lca(int x, int y)
{
    if (deep[x] != deep[y])
    {
        if (deep[x] < deep[y])swap(x, y);
        for (int i = 20; i >= 0; i--)
        {
            if (deep[fa[x][i]] >= deep[y])x = fa[x][i];
        }
    }
    if (x == y)return x;
    for (int i = 20; i >= 0; i--)
    {
        int a = fa[x][i], b = fa[y][i];
        if (a != b)
        {
            x = a, y = b;
        }
    }
    return fa[x][0];
}

void dfs(int x, int y)
{
    fa[x][0] = y;
    for (int i = 1; i < 20; i++)
    {
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
    }
    for (auto& i : tree[x])
    {
        if (i == y)continue;
        deep[i] = deep[x] + 1;
        //i点到1的间隔便是：父节点到1的间隔+父节点到它的间隔
        dis[i] = dis[x] + mymap[x][i];
        dfs(i, x);
    }
}

void solve()
{
    //由于是多组数据，所以每次要把stl清空
    tree->clear();
    mymap.clear();
    int n, m, x, y, w;
    cin >> n >> m;
    for (int i = 1; i < n; i++)
    {
        cin >> x >> y >> w;
        tree[y].push_back(x);
        tree[x].push_back(y);
        mymap[x][y] = w;
        mymap[y][x] = w;
    }
    //标题没给咱们root，咱们设1为根
    deep[1] = 1;
    dfs(1, 0);
    while (m--)
    {
        cin >> x >> y;
        int z = lca(x, y);
        cout << dis[x] + dis[y] - dis[z] * 2 << endl;
    }
}

signed main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cout.tie(nullptr);
   int t = 1;
   cin >> t;
   while (t--)
   {
     solve();
   }
   return 0;
}

六、结束

看到这儿恭喜你又学会了一个新的知识点，鼓掌（啪啪啪啪）

不过我想说的是，学习一个新的知识点不难，难的是怎样玩出花来。

光看文章或视频肯定是不行的，这些仅仅帮你入门的媒介，更重要的是你后续的尽力，只要多些题积累经验，才干更好的把握知识点。

千言万语汇成一句话——多刷题！

最终假如本篇文章帮到了您，不知是否能点一个小小的赞呢。（拜托了！这对我真的很重要！）

那么咱们鄙人一个知识点再见啦！拜拜！

倍增？最近公共祖先？——从定义到实现，帮你一步步吃掉它！

倍增？最近公共先人？——从定义到实现，帮你一步步吃掉它！

一、倍增倍增——翻倍的增加

让咱们来看看倍增是怎样处理的：

二、公共先人——这玩意还能公共吗

在同一颗树上，两个不同节点去往根节点时会经过的相同节点。

三、求先人——喂你咋跪下了

数据量小还好说，数据量大那是妥妥的死。所以咱们要想办法去优化它。

为了便利处理这一状况，咱们借用了树状结构中——“深度”的概念，即一个节点到根节点的间隔。

不过还有个之前被咱们忽视的问题：咱们该怎样记录途径？

这儿咱们还是选用的倍增的思维：

至此，倍增思维求最近公共先人的办法咱们现已全部学会了，接下来让咱们——

四、用代码实现

五、给我题！我要试一试！

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

AC代码

Problem – 2586 (hdu.edu.cn)

用一个数组dis记录下来，dis[i]表明节点i到根节点的间隔为dis[i]:

AC代码

六、结束

不过我想说的是，学习一个新的知识点不难，难的是怎样玩出花来。

千言万语汇成一句话——多刷题！

最终假如本篇文章帮到了您，不知是否能点一个小小的赞呢。（拜托了！这对我真的很重要！）

作者信息

推广

倍增？最近公共祖先？——从定义到实现，帮你一步步吃掉它！

倍增？最近公共先人？——从定义到实现，帮你一步步吃掉它！

一、倍增倍增——翻倍的增加

让咱们来看看倍增是怎样处理的：

二、公共先人——这玩意还能公共吗

在同一颗树上，两个不同节点去往根节点时会经过的相同节点。

三、求先人——喂你咋跪下了

数据量小还好说，数据量大那是妥妥的死。所以咱们要想办法去优化它。

为了便利处理这一状况，咱们借用了树状结构中——“深度”的概念，即一个节点到根节点的间隔。

不过还有个之前被咱们忽视的问题：咱们该怎样记录途径？

这儿咱们还是选用的倍增的思维：

至此，倍增思维求最近公共先人的办法咱们现已全部学会了，接下来让咱们——

四、用代码实现

五、给我题！我要试一试！

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

AC代码

Problem – 2586 (hdu.edu.cn)

用一个数组dis记录下来，dis[i]表明节点i到根节点的间隔为dis[i]:

AC代码

六、结束

不过我想说的是，学习一个新的知识点不难，难的是怎样玩出花来。

千言万语汇成一句话——多刷题！

最终假如本篇文章帮到了您，不知是否能点一个小小的赞呢。（拜托了！这对我真的很重要！）

相关文章

技术该有的业务产品思维

认知史 6：迷茫时的自处方式

想玩原生的 C 老师，自搭 🪜 踩坑记录

AnimationPreviewer – 快速预览Lottie&SVGA的Mac小工具

作者信息

推广