欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 房产 > 建筑 > 【C++】倍增LCA详解 + P3379 最近公共祖先题解

【C++】倍增LCA详解 + P3379 最近公共祖先题解

2024/11/30 12:48:14 来源:https://blog.csdn.net/YLCHUP/article/details/140742655  浏览:    关键词:【C++】倍增LCA详解 + P3379 最近公共祖先题解

文章目录

    • 1.暴力做法
    • 2.倍增做法
      • 问题1
      • 问题2
    • 总结
    • Code
    • End

这道题是一道求树上最近公共祖先的模板题。

1.暴力做法

我们先思考O(n)的暴力做法:(这里的n是指树的最大深度,也可以近似于节点个数)

我们假设我们要求的是lca(u,v),那么可以考虑让u,v首先跳到同一深度,然后一同向上走,每次走一步额,直到节点重合为止
可以知道我们一定会找到lca,因为如果前面所有的都找不到,那也一定会汇聚在根节点

这样是线性复杂度,在多次查询的题目里会有O(n^2)的复杂度,显然还不够。

我们考虑优化:使用倍增算法。

2.倍增做法

倍增,其底层原理是根据二进制优化枚举,因为一个数一定可以根据二进制拆成2的幂次相加的形式

所以,我们只要每次都往上跳2的幂次步,那复杂不就优化到O(logn)了吗?

这显然可行,我们先让u,v跳到同一深度:预处理深度差d,如果d的第i位二进制为1,就往上跳2^i步,
然后再两个一同往上跳,同上,每次跳2的幂次步即可

这时候,又出现了两个问题:

  1. 如何在O(1)的复杂度跳到当前节点的第2^i次方个节点?
  2. 我们并不知道lca(u,v)和u,v的深度差,那如何根据二进制往上跳呢?

问题1

可以通过O(n)的预处理实现。设f[u][i]表示节点u向上跳2^i步到的节点

我们对整棵树跑dfs,同时,对于节点u,记录u的深度dep[u],
转移f数组:f[u][i] = f[f[u][i-1]][i-1] 1<=i<=log2(dep[u]) ……对节点u上方的所有节点都预处理
(注意取值范围从1开始,因为从0开始的话,i-1可能越界。处理方法只要在递归u的父亲节点k时把f[u][0]=k即可)

这个转移十分巧妙,原理: 2 i − 1 + 2 i − 1 = 2 i 2^{i-1}+2^{i-1}=2^i 2i1+2i1=2i
节点u向上跳 2 i 2^i 2i 步=节点u向上跳 2 i − 1 2^{i-1} 2i1 步的节点v 向上跳 2 i − 1 2^{i-1} 2i1 步的位置
因为我们从上向下遍历树,同时枚举i也是从小到大枚举,所以不会出现转移的状态没有的情况。

问题2

首先思路1:发现这个问题具有单调性,可以二分
因为,如果lca(u,v)=k,则k的所有祖先也都是(u,v)的公共祖先。所以可以二分向上跳的高度
但这样复杂度是 ( log ⁡ n ) 2 (\log n)^2 (logn)2 的,我们还可以优化成单log

思路2:
我们可以直接从大到小枚举log2(dep[u])次(注意此时dep[u]==dep[v]),只要f[u][i]!=f[v][i]就继续向上跳,这样一定能到达

原因:从大到小凑一定可以凑出所有的数,因为对于偶数可以拆成若干次 2 i 2^i 2i 到达;奇数可以先走若干次 2 i 2^i 2i ,再用一个 2 0 = 1 2^0=1 20=1 到达
例如u,v和lca的深度差为 5 = 2 0 + 2 1 + 2 1 = 2 0 + 2 2 5=2^0+2^1+2^1=2^0+2^2 5=20+21+21=20+22,从小到大根本不知道这个 2 1 2^1 21 要来几次;但从大到小来可以直接先用 2 2 2^2 22,再用 2 1 2^1 21

在写代码时,因为直接判等可能会出错,我们可以根据上面的凑数原理,凑最后一个两个fa不等的位置,这样,在这个位置再往上走一步就一定是答案

至此,倍增思想和LCA的完美结合结束!

总结

要点:

  1. 倍增本质上也是一种dp,常用状态:f[i][j]表示第i个位置后2^j个位置的……,
    常用转移:f[i][j]=f[f[i-1][j 不定]][j-1]

  2. 上面提到倍增也可以用二分来实现,因为二分和倍增可以看作两个相反的操作。

    二分是从大区间不断折半(21,22,…2^k)到小区间来实现查找,而倍增是从小区间倍到大区间。

    所以很多二分的题目也可以用倍增,只要构建好递推关系即可

Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 7;vector <int> T[maxn];
int f[maxn][25]; // 2^20≈1e6
int dep[maxn];void dfs(int u){ // f[u][0]就相当于父亲节点,即u往上2^0=1个节点dep[u] = dep[f[u][0]] + 1;for(int i = 1; i <= log2(dep[u]); i ++){ // 从1开始,因为f[u][0]在本次递归开始之前就确定了,同时i=0时i-1会越界f[u][i] = f[f[u][i - 1]][i - 1];}for(int v : T[u]){if(v == f[u][0]) continue;f[v][0] = u; // 提前处理一下dfs(v);}
}int lca(int u, int v){// 让u为较深的那个点,便于计算if(dep[u] < dep[v]) swap(u, v);// 让u跳到与v相同的高度int d = dep[u] - dep[v];for(int i = 0; i <= log2(d); i ++){ // 枚举每一个二进制位if(d >> i & 1){u = f[u][i];}}if(u == v) return u; // 特判此时已经相等的情况s// 同时向上跳,直到相等for(int i = log2(dep[u]); i >= 0; i --){ // 注意倒着枚举if(f[u][i] != f[v][i]){u = f[u][i], v = f[v][i];}}return f[u][0]; // 因为我们前面找到的一定是最后一个不相等的fa,所以再往后一个一定就是答案
}void solve()
{int n, m, s; cin >> n >> m >> s;for(int x, y, i = 1; i <= n - 1; i ++){cin >> x >> y;T[x].push_back(y);T[y].push_back(x);}// 预处理节点深度、倍增数组dfs(s);// 处理询问for(int a, b, i = 1; i <= m; i ++){cin >> a >> b;cout << lca(a, b) << '\n';}
}signed main()
{ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);solve();return 0;
}

End

经过这么详细的讲解,大家一定对倍增LCA有了些许了解吧。

这里是 YLCHUP,谢谢大家,拜拜ヾ(•ω•`)o

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com