当前位置:网站首页>(树) 最近公共祖先(LCA)
(树) 最近公共祖先(LCA)
2022-07-31 03:20:00 【天赐细莲】
前言
如这个问题的名字一样,我们的目的是为了求得一个树上两个点得最近公共祖先
通常对于树的操作那自然是离不开搜索,其中dfs的理解和编写必须了熟于心
解决LCA的算法常见的有三种,Tarjan,树链剖分,倍增算法
参考资料:
322 最近公共祖先 Tarjan算法_哔哩哔哩_bilibili
下表也是董晓老师整理
倍增算法 Tarjan算法 树链剖分 数据结构 fa[][], dep[]
fa[], vis[], query[], ans[]
fa[], dep[], sz[], son[], top[]
算法 倍增法
深搜打表,跳跃查询并查集
深搜, 回时指父, 离时搜根重链剖分
两遍深搜打表,跳跃查询时间复杂度 O ( ( n + m ) l o g n ) {O((n+m)logn)} O((n+m)logn) O ( n + m ) {O(n+m)} O(n+m) O ( n + m l o g n ) {O(n+mlogn)} O(n+mlogn) 其中,倍增算法的效率偏低些
Tarjan是离线算法
树链剖分需要dfs两次
可以说每种算法都各有特点
练习题:
本文代码针对本题:洛谷:P3379 【模板】最近公共祖先(LCA)
杭电:2586 How far away ? 本题是带有权值的
具体算法
Tarjan
Tarjan 是一种离线算法
这里巧妙利用到了并查集的帮助
先记录所有的查询状态,强制转化为离线算法
在每次dfs完子节点后,让子节点的并查集指向当前节点 (子->父)
在当前节点dfs完毕后,检查搜索集,是否有对应的查询点
若存在,且已经访问过,则表示对应点的并查集已经记录了
此时可以记录对应查询组的lca,注意这里一定要写路径压缩的并查集
因为我们可以通过不断的压缩,将并查集的指向不断的往树的上方指
最终确保压缩到目标的lca
/** * https://www.luogu.com.cn/problem/P3379 * P3379 【模板】最近公共祖先(LCA) * Tarjan */
#include <bits/stdc++.h>
using namespace std;
const int M = 10 + 5 * 100000;
vector<vector<int>> graph(M); // 存图(树)
vector<vector<pair<int, int>>> query(M); // 询问
int father[M]; // 并查集
bool vis[M]; // vis
int ans[M]; // 第几组询问的答案
void initUnionFind(int n) {
for (int i = 0; i <= n; i++) {
father[i] = i;
}
}
// 必须路径压缩
int unionFind(int x) {
return x == father[x] ? x : father[x] = unionFind(father[x]);
}
// Tarjan 算法
void Tarjan(int cur) {
vis[cur] = true;
for (int& nex : graph[cur]) {
if (!vis[nex]) {
Tarjan(nex);
// 核心 nex 指向 cur
father[nex] = cur;
}
}
// 递归完毕
for (auto& it : query[cur]) {
int &to = it.first, &idx = it.second;
// 若访问过,则可以记录
if (vis[to]) {
ans[idx] = unionFind(to);
}
}
}
int main() {
// 边数 询问数 根节点
int n, m, root;
scanf("%d %d %d", &n, &m, &root);
// 初始化并查集
initUnionFind(n);
// 存无向图
for (int i = 1, u, v; i <= n - 1; i++) {
scanf("%d %d", &u, &v);
graph[v].emplace_back(u);
graph[u].emplace_back(v);
}
// 离线算法,先知道所有情况,再算
// 询问 也要双向存
for (int i = 1, x, y; i <= m; i++) {
scanf("%d %d", &x, &y);
query[x].emplace_back(y, i);
query[y].emplace_back(x, i);
}
Tarjan(root);
for (int i = 1; i <= m; i++) {
printf("%d\n", ans[i]);
}
return 0;
}
树链剖分
树链剖分 分为很多种,这里写的是重链剖分
这里的重表示的是当前树的节点的数量
当某个子树的数量是所有子树中最多的时候,这个节点就是所谓的重孩子
那么当前点就是这个重子树中所有点的重链头
其余的子树再单独自立门户开辟重链
在求lca时,不断靠着链头节点的跳跃,跨过大量的节点
dfs1()
主要获得
son[], father[], deep[]
其中size[]
是辅助搜索出son[]
用的
dfs2()
借助
son[]和father[]
求出top[]
(重链的头)
lca()
首先明确一点,重链头的链头节点就是本身
不断判断两个点的链头是否相等
若不等则让深度更深的点跳跃到链头的父节点
这样深点就能向根节点靠近很多,且能更新到新的链中,可以重新判断了
最终,当两者的链头相等时候,返回深度较低的点,获得lca
/** * https://www.luogu.com.cn/problem/P3379 * P3379 【模板】最近公共祖先(LCA) * 树链剖分 (重链) */
#include <bits/stdc++.h>
using namespace std;
const int M = 10 + 5 * 100000;
vector<vector<int>> graph(M); // 图
vector<int> father(M); // 父节点
vector<int> son(M); // 重孩子
vector<int> size(M); // 子树节点个数
vector<int> deep(M); // 深度,根节点为1
vector<int> top(M); // 重链的头,祖宗
void dfs1(int cur, int from) {
deep[cur] = deep[from] + 1; // 深度,从来向转化来
father[cur] = from; // 父节点,记录来向
size[cur] = 1; // 子树的节点数量
son[cur] = 0; // 重孩子 (先默认0表示无)
for (int& to : graph[cur]) {
// 避免环
if (to == from) {
continue;
}
// 处理子节点
dfs1(to, cur);
// 节点数量叠加
size[cur] += size[to];
// 松弛操作,更新重孩子
if (size[son[cur]] < size[to]) {
son[cur] = to;
}
}
}
void dfs2(int cur, int grandfather) {
top[cur] = grandfather; // top记录祖先
// 优先dfs重儿子
if (son[cur] != 0) {
dfs2(son[cur], grandfather);
}
for (int& to : graph[cur]) {
// 不是cur的父节点,不是重孩子
if (to == father[cur] || to == son[cur]) {
continue;
}
// dfs轻孩子
dfs2(to, to);
}
}
int lca(int x, int y) {
// 直到top祖宗想等
while (top[x] != top[y]) {
// 比较top祖先的深度,x始终设定为更深的
if (deep[top[x]] < deep[top[y]]) {
swap(x, y);
}
// 直接跳到top的父节点
x = father[top[x]];
}
// 在同一个重链中,深度更小的则为祖宗
return deep[x] < deep[y] ? x : y;
}
int main() {
// 边数 询问数 根节点
int n, m, root;
cin >> n >> m >> root;
// 该树编号 [1, n]
// 本题仅仅说有边,未说方向
for (int i = 1, u, v; i <= n - 1; i++) {
cin >> u >> v;
graph[v].emplace_back(u);
graph[u].emplace_back(v);
}
// 树链剖分 重链
dfs1(root, 0);
dfs2(root, root);
for (int i = 1, x, y; i <= m; i++) {
cin >> x >> y;
cout << lca(x, y) << endl;
}
return 0;
}
倍增算法
倍增
cin, cout
不能过
倍增算法 本质是一种借助二进制的动态规划,而这里又是对树的操作,也可以说是一道树形dp了
通常定义
father[i][j]
表示i到j
的状态,而这里倍增的j指的是2的倍数即
2^j
,以二进制成倍的增加,这就是所谓的倍增
dfs
这里的dfs主要是以深度来进行倍增
由父亲跳到爷爷,由爷爷跳到高祖父
由于是dfs我们可以先处理辈分高的节点
之后的递归可以借助已经处理的高辈分节点来打倍增表
lca
这里的搜索主要也是通过将高深度拉回低深度的方式处理
先处理两者中的高深度节点
由于任何一个十进制数都能分解成二进制,因此必然能跳走我们需要的距离
我们先跳大步,在跳小步可以保证跑一遍循环就能达到我们的目标位置
跳完后先特判走两个节点重合的情况
此时,两个点的高度是相等的,那就两者一起往上跳。
注意我们只能一起跳到lca的下一层节点
若继续跳下去,最后必然是一起跳到root,那就没有任何意义了
/** * https://www.luogu.com.cn/problem/P3379 * P3379 【模板】最近公共祖先(LCA) * 倍增算法 * cin cout 超时 */
#include <bits/stdc++.h>
using namespace std;
const int M = 10 + 100000 * 5;
// log2(5e5 + 10) = 18.9
vector<vector<int>> graph(M); // 存图
vector<int> deep(M); // 深度
vector<vector<int>> father(M, vector<int>(20)); // i点跳2^j步到达的点(点号)
void dfs(int cur, int from) {
deep[cur] = deep[from] + 1; // 深度 + 1
father[cur][0] = from; // 跳2^0=1步就是直接的父节点
// 借助上一层的父节点跳到爷爷节点
int log = log2(M + 1);
for (int i = 1; i <= log; i++) {
father[cur][i] = father[(father[cur][i - 1])][i - 1];
}
for (int& nex : graph[cur]) {
if (nex == from) {
continue;
}
dfs(nex, cur);
}
}
int lca(int u, int v) {
// u设为深度大的点,对u进行跳步
if (deep[u] < deep[v]) {
swap(u, v);
}
// 计算一下深度,过滤掉部分循环
// +1保精度
int log = log2(deep[u] + 1);
// 二进制拆分,先跳大步
// 将深度大的跳到同一深度
for (int i = log; i >= 0; i--) {
if (deep[father[u][i]] >= deep[v]) {
u = father[u][i];
}
}
// v正好是u的lca,可以直接return
if (u == v) {
return v;
}
for (int i = log; i >= 0; i--) {
// 有父节点,才可能跳
// 实际可以省略,因为是同层,都是0则if为false
// 父节点不同则要跳
if (father[u][i] != 0 && father[u][i] != father[v][i]) {
u = father[u][i];
v = father[v][i];
}
}
// 退出循环时,保证两个点在lca的正下方同一层
return father[u][0];
}
int main() {
// 边数 询问数 根节点
int n, m, root;
scanf("%d %d %d", &n, &m, &root);
// 该树编号 [1, n]
// 本题仅仅说有边,未说方向
for (int i = 1, u, v; i <= n - 1; i++) {
scanf("%d %d", &u, &v);
graph[v].emplace_back(u);
graph[u].emplace_back(v);
}
// 预处理倍增的father[i][2^j]和deep[]
dfs(root, 0);
for (int i = 1, x, y; i <= m; i++) {
scanf("%d %d", &x, &y);
printf("%d\n", lca(x, y));
}
return 0;
}
END
边栏推荐
猜你喜欢
7年经验,功能测试工程师该如何一步步提升自己的能力呢?
Key Technologies of Interface Testing
5. How does the SAP ABAP OData service support the $filter operation
「 每日一练,快乐水题 」1331. 数组序号转换
【Exception】The field file exceeds its maximum permitted size of 1048576 bytes.
Mysql 45讲学习笔记(二十五)MYSQL保证高可用
postgresql 15源码浅析(5)—— pg_control
【异常】The field file exceeds its maximum permitted size of 1048576 bytes.
CorelDRAW2022 streamlined Asia Pacific new features in detail
Mysql 45讲学习笔记(二十四)MYSQL主从一致
随机推荐
addressable in Golang
安全20220722
els 方块向左移动条件判断
下载jar包的好地方
Redis implements distributed locks
What is a distributed lock?Three ways of implementing distributed lock
The distance value between two arrays of LeetCode simple questions
[Compilation principle] Lexical analysis program design principle and implementation
5. SAP ABAP OData 服务如何支持 $filter (过滤)操作
WebSocket Session is null
Good place to download jar packages
els block to the left to move the conditional judgment
LeetCode每日一练 —— OR36 链表的回文结构
els 方块向右移动边界判断、向下加速
【AUTOSAR-RTE】-4-Port和Interface以及Data Type
安全20220709
SQL injection Less47 (error injection) and Less49 (time blind injection)
Mysql 45讲学习笔记(二十三)MYSQL怎么保证数据不丢
Mysql 45 study notes (twenty-four) MYSQL master-slave consistency
浅识Flutter 基本组件之showDatePicker方法