当前位置：首页 > article >正文

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

article 2024/11/13 6:41:13

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

一、倍增倍增——翻倍的增长

倍增是一种思想，实际上的操作就是通过不断翻倍来缩短我们的处理时间：

它可以把线性级别的处理优化到指数级。

举个栗子：

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

未命名绘图.png

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

让我们来看看倍增是怎么处理的：

未命名绘图1.png

未命名绘图2.png

未命名绘图3.png

未命名绘图4.png

未命名绘图5.png

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

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

这样处理，到了最后我们就会离目的地无限接近，那么只要再一步，就可以到达目的地了。

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

倍增的思想其实非常简单，但是重点是该如何去使用它。

接下来让我们看看——

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

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

我们这里的公共祖先，通俗理解就是：

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

比如在这棵树中:

未命名绘图6.png

节点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节点的公共祖先的？

未命名绘图6.png

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

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

我们看一看这样做的时间复杂度：

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

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

这里我们采用的便是倍增法了。（别忘了我们的“擦边球”操作）

未命名绘图7.png
未命名绘图8.png
未命名绘图9.png
未命名绘图10.png
未命名绘图11.png

但是这样做其实有个问题，比如求节点2和节点3的公共祖先：

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

我们可以发现，如果此时我们一起移动，那么结果会是错误的，因为它们并没有同时相等的路径节点。

这是因为它俩到根节点的路径并不一样长，为了解决这个问题，我们应该保证节点2和3的剩余路径一样长。

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

为了方便处理这一情况，我们借用了树状结构中——“深度”的概念，即一个节点到根节点的距离。

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

这就是通过倍增法求解最近公共祖先的做法了。

不过还有个之前被我们忽视的问题：我们该怎么记录路径？

如果每个节点都开个数组来存路径节点，占空间不说，实际操作起来也很慢。而且我们可以发现，并不是路径上所有的节点我们都需要，我们只需要每个节点的：第2^0个、第21个、第2^{2个、……、第2}k个祖先就行。

这里我们还是采用的倍增的思想：

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

比如这样一棵树：

未命名绘图12.png

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

那么该如何推出这么一个公式呢？

我们可以发现：

未命名绘图13.png

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]:

未命名绘图15.png

如果我们想求点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;
}