最近公共祖先(LCA)
最近公共祖先(LCA)是一种树形数据结构的算法，用于在一棵树或图中找到两个节点的最近公共祖先。
朴素算法
逐级向上遍历，直到找到两个节点的公共祖先。
先对树进行预处理，得到每个节点的父节点和深度。时间复杂度为 $O(n)$。
之后，对于每个查询，从根节点开始，逐级向上遍历，直到找到两个节点的公共祖先。时间复杂度为 $O(mh)$。
总时间复杂度为 $O(n+mh)$，其中 n 为节点数，m 为查询数，h 为树的高度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 预处理O(n)
void bfs(int root){
q.push(root);
vis[root] = true; // 记录当前节点已访问
dep[root] = 0; // 记录当前节点的深度
fa[root] = -1; // 记录当前节点的父节点
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : g[u]){
if (vis[v]) {
continue;
}
vis[v] = true;
dep[v] = dep[u] + 1;
fa[v] = u;
q.push(v);
}
}
}
// 查询O(m * h)
int lca(int a, int b){
while (dep[a] > dep[b]){
a = fa[a];
}
while (dep[b] > dep[a]){
b = fa[b];
}
while (a != b){
a = fa[a];
b = fa[b];
}
return a;
}
倍增算法
还没学会，先放着。
Tarjan算法
tarjan算法解决LCA问题 测试链接：https://www.luogu.com.cn/problem/P3379 算法过程： 1)处理所有问题，建好每个节点的问题列表，然后遍历树 2)来到当前节点u,令visited[u]=true，表示当前节点已经访问 3)遍历u的所有子树，每棵子树遍历完都和u节点合并成一个集合，集合设置u做头节点 4)遍历完所有子树后，处理关于u节点的每一条查询(v, id) 如果发现v已经访问过，u和v的最低公共祖先=u所在集合的头节点 如果发现v没有访问过，那么当前查询先不处理，等到v节点时再去处理查询(v, id)得到答案
如果节点数 n，查询数量 m，过程总的时间复杂度 $O(n+m)$，但是只能做批量离线查询
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void tarjan(int u, int fa) {
vis[u] = true; // ① 标记已访问
// ② 深度优先遍历子树
for (int v : g[u]) {
if (v == fa)
continue;
tarjan(v, u); // ③ 递归处理子树
merge(v, u); // ④ 合并子树到当前节点(并查集) v合并至u
}
// ⑤ 处理当前节点的所有查询
for (auto t : queries[u]) {
int v = t.first;
int id = t.second;
if (vis[v]) { // ⑥ 仅当对方节点已访问时处理
ans[id] = findHead(v); // ⑦ 通过并查集获取LCA
}
}
}
