LCA
最近公共祖先简称 LCA(Lowest Common Ancestor)。两个节点的最近公共祖先,就是这两个点的公共祖先里面,离根最远的那个。
朴素算法:第一步通过DFS算出每个节点的深度;2. 平均两点的深度;3. 两个点都不断往上找父节点,直到相遇。朴素算法复杂度最坏是\(O(n)\),但对于随机树,复杂度是\(O(\log n)\)。
倍增法(Binary Lifting) 求 LCA
朴素算法最大问题是第2、3步一次移动一层,线性查找复杂度过高,通过预处理,可以加快移动速度。
倍增的具体办法:
- 预先计算祖先指针表:每个节点的上一辈祖先,上两辈祖先,上四辈祖先,上八辈祖先,…,上\(2^k\)辈祖先。
- 平均两点的深度,这里已经可以利用祖先指针表快速移动。
- 二分查找LCA,从最远的指针开始尝试(可以理解成从高位开始依次尝试改变二进制位),如果不导致路径重合,就follow这个指针(等价于改变对应二进制位)。
例题
这个问题就是在一棵树里面求任两点的距离,解法就是先求两点的LCA,然后利用以下性质可以直接算出距离:\(d(u,v)=h(u)+h(v)-2h(LCA(u,v))\),其中\(d(u,v)\)是树上两点间的距离,\(h(u)\)代表某点到树根的距离。
实现:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#define MXN 50007
using namespace std;
std::vector<int> v[MXN];
std::vector<int> w[MXN];
// fa是倍增指针,cost是对应指针的路径长度,dep是每个结点的深度
int fa[MXN][31], cost[MXN][31], dep[MXN];
int n, m;
int a, b, c;
// dfs,用来为 lca 算法做准备。接受两个参数:dfs 起始节点和它的父亲节点。
void dfs(int root, int fno) {
// 初始化:第 2^0 = 1 个祖先就是它的父亲节点,dep 也比父亲节点多 1。
fa[root][0] = fno;
dep[root] = dep[fa[root][0]] + 1;
// 初始化:其他的祖先节点:第 2^i 的祖先节点是第 2^(i-1) 的祖先节点的第
// 2^(i-1) 的祖先节点。
for (int i = 1; i < 31; ++i) {
fa[root][i] = fa[fa[root][i - 1]][i - 1];
cost[root][i] = cost[fa[root][i - 1]][i - 1] + cost[root][i - 1];
}
// 遍历子节点来进行 dfs。
int sz = v[root].size();
for (int i = 0; i < sz; ++i) {
if (v[root][i] == fno) continue;
cost[v[root][i]][0] = w[root][i];
dfs(v[root][i], root);
}
}
// lca。用倍增算法算取 x 和 y 的 lca 节点。
int lca(int x, int y) {
// 令 y 比 x 深。
if (dep[x] > dep[y]) swap(x, y);
// 令 y 和 x 在一个深度。
int tmp = dep[y] - dep[x], ans = 0;
for (int j = 0; tmp; ++j, tmp >>= 1)
if (tmp & 1) ans += cost[y][j], y = fa[y][j];
// 如果这个时候 y = x,那么 x,y 就都是它们自己的祖先。
if (y == x) return ans;
// 不然的话,找到第一个不是它们共同祖先的两个点,也就是LCA下面一层的两个结点。
// 这个就是从高位开始依次尝试改变二进制位,如果不导致路径重合,就改变之。
for (int j = 30; j >= 0 && y != x; --j) {
if (fa[x][j] != fa[y][j]) {
ans += cost[x][j] + cost[y][j];
x = fa[x][j];
y = fa[y][j];
}
}
// 返回结果。
ans += cost[x][0] + cost[y][0];
return ans;
}
int main() {
// 初始化表示祖先的数组 fa,代价 cost 和深度 dep。
memset(fa, 0, sizeof(fa));
memset(cost, 0, sizeof(cost));
memset(dep, 0, sizeof(dep));
// 读入树:节点数一共有 n 个。
scanf("%d", &n);
for (int i = 1; i < n; ++i) {
scanf("%d %d %d", &a, &b, &c);
++a, ++b;
v[a].push_back(b);
v[b].push_back(a);
w[a].push_back(c);
w[b].push_back(c);
}
// 为了计算 lca 而使用 dfs。
dfs(1, 0);
// 查询 m 次,每一次查找两个节点的 lca 点。
scanf("%d", &m);
for (int i = 0; i < m; ++i) {
scanf("%d %d", &a, &b);
++a, ++b;
printf("%d\n", lca(a, b));
}
return 0;
}
Shawn的笔记有配图,写的比较清楚。
用欧拉序列转化为RMQ求LCA
对一棵树进行 DFS,无论是第一次访问还是回溯,每次到达一个结点时都将编号记录下来,可以得到一个长度为 \(n-1\) 的序列,这个序列被称作这棵树的欧拉序列。
在下文中,把结点 \(u\) 在欧拉序列中第一次出现的位置编号记为 \(pos(u)\) (也称作节点 \(u\) 的欧拉序),把欧拉序列本身记作 \(E[1..2n-1]\)。
有了欧拉序列,LCA 问题可以在线性时间内转化为 范围最小值(Range Minimal Query, RMQ) 问题,即 \(pos[LCA(u,v)]=min{pos(k)|k \in E[pos(u)..pos(v)]}\)。
欧拉序列图示 (用最小\(pos\)或最小深度来求都是可以的,上面文字是\(pos\),图示中是最小深度)
实现:
int dfn[N << 1], dep[N << 1], dfntot = 0;
void dfs(int t, int depth) {
dfn[++dfntot] = t;
pos[t] = dfntot;
dep[dfntot] = depth;
for (int i = head[t]; i; i = side[i].next) {
dfs(side[i].to, t, depth + 1);
dfn[++dfntot] = t;
dep[dfntot] = depth;
}
}
void st_preprocess() {
lg[0] = -1; // 预处理 lg 代替库函数 log2 来优化常数
for (int i = 1; i <= (N << 1); ++i) lg[i] = lg[i >> 1] + 1;
for (int i = 1; i <= (N << 1) - 1; ++i) st[0][i] = dfn[i];
for (int i = 1; i <= lg[(N << 1) - 1]; ++i)
for (int j = 1; j + (1 << i) - 1 <= ((N << 1) - 1); ++j)
st[i][j] = dep[st[i - 1][j]] < dep[st[i - 1][j + (1 << i - 1)]
? st[i - 1][j]
: st[i - 1][j + (1 << i - 1)];
}
直接调用dfs()完成初始化后,当我们需要查询某点对 \(u,v\) 的 LCA 时,查询区间 \(pos(u), pos(v)\) 上最小值(pos或depth都可以)的所代表的节点即可。
进一步优化使用Segment Tree线段树,调用dfs()后再调用st_preprocess()即得到查询用的ST树,这时预处理复杂度\(O(n\log n)\),查询复杂度\(O(1)\)。
习题
- P3379 【模板】最近公共祖先(LCA) 普及/提高-
- P2420 让我们异或吧 普及/提高-
- P3128 [USACO15DEC]Max Flow P 普及+/提高
- P6869 [COCI2019-2020#5] Putovanje 普及+/提高
- P5836 [USACO19DEC]Milk Visits S 普及/提高-
- P1967 [NOIP2013 提高组] 货车运输 提高+/省选-
- P7103/T245112 「C.E.L.U-01」族谱树 求第k层孩子的LCA 普及+/提高
- P1084/T245113 [NOIP2012 提高组] 疫情控制 省选/NOI-
- P1600/T245122 [NOIP2016 提高组] 天天爱跑步 省选/NOI-
- P2680 [NOIP2015 提高组] 运输计划 省选/NOI-