acwing算法提高之图论--最近公共祖先

1 介绍

本博客用来记录"对于有根图中，求最近公共祖先"的题目。

求解方法：

1. 向上标记法。每次求两个结点的最近公共祖先的时间复杂度是O(N)。由于时间复杂度较高，通常不用。
2. 倍增法。

倍增法重要思路：预处理出两个数组fa[i][j]和depth[i]。其中fa[i][j]表示从i开始，向上走2^j步所能走到的结点。0<=j<=logn。depth[i]表示深度，为到根结点的距离再加上1。

哨兵：如果从i开始跳2^j步会跳过根结点，那么fa[i][j] = 0，depth[0] = 0。

倍增法重要步骤：

1. 先将两个点跳到同一层。
2. 让两个点同时往上跳，一直跳到它们的最近公共祖先的下一层。

倍增法的时间复杂度分析：预处理的时间复杂度为O(NlogN)，查询的时间复杂度为O(logN)。

2 训练

题目1：1172祖孙询问

C++代码如下，

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>using namespace std;const int N = 40010;
int n, m;
int depth[N], fa[N][16];
int ancestor;
unordered_map<int, vector<int>> g;void bfs(int root) {memset(depth, 0x3f, sizeof depth);depth[0] = 0;depth[root] = 1; queue<int> q;q.push(root);while (!q.empty()) {int a = q.front();q.pop();for (auto b : g[a]) {if (depth[b] > depth[a] + 1) {depth[b] = depth[a] + 1;q.push(b);fa[b][0] = a;for (int k = 1; k <= 15; ++k) {fa[b][k] = fa[fa[b][k-1]][k-1];}}}}return;
}int lca(int a, int b) {//倍增法if (depth[a] < depth[b]) swap(a, b);for (int k = 15; k >= 0; --k) {if (depth[fa[a][k]] >= depth[b]) {a = fa[a][k];}}if (a == b) return a;for (int k = 15; k >= 0; --k) {if (fa[a][k] != fa[b][k]) {a = fa[a][k];b = fa[b][k];}}return fa[a][0];
}int main() {cin >> n;int a, b;for (int i = 0; i < n; ++i) {cin >> a >> b;if (b == -1) {ancestor = a;} else {g[a].emplace_back(b);g[b].emplace_back(a);        }}cin >> m;vector<pair<int,int>> queries;for (int i = 0; i < m; ++i) {cin >> a >> b;queries.emplace_back(a,b);}//从根结点开始遍历bfs(ancestor);for (auto [a, b] : queries) {int x = lca(a, b);if (a == x) {puts("1");} else if (b == x) {puts("2");} else {puts("0");}}return 0;
}

题目2：1171距离

C++代码如下，