前置知识
- DFN序：对一棵树进行深度优先搜索
DFS得到的结点序列，即深度优先搜索DFS的访问顺序。该表述不一定严谨，建议百度 - ST表（Sparse Table，稀疏表）
算法概述
引理 1.1
在 DFN序 中祖先一定出现后代之前。
考虑一树上的两个节点 \(x\)，\(y\) 的最近公共祖先 \(d\) ，设 \(x\) 的 DFN序 小于等于 \(y\) 的 DFN序。
当 \(x\) 不为 \(y\) 的祖先时
由 引理1.1 可得，\(d\) 及其祖先的 DFN 序不在 DFN 序的 \([x,y]\) 区间内。
设 \(d\) 一儿子 \(d'\)，包含该儿子且以 \(d\) 为根的子树 包含 \(v\)。
显然，\(d'\) 的 DFN 序属于 DFN 序的 \([x,y]\) 区间，即在 DFN 序的 \([x,y]\) 区间内寻找 DFN 序最小的一个节点，那个点的父亲就是 \(d\)。
当 \(x\) 为 \(y\) 的祖先时
那么只需由 在 DFN 序的 \([x,y]\) 区间内寻找 变为 在 DFN 序的 \([x - 1,y]\) 区间内寻找。
因为 当 \(x\) 不为 \(y\) 的祖先时 \(x\neq y\) 所以 算法微调后正确性仍能保证。
需要注意的是，当 \(x=y\) 时，需要特判。
综上所述，当 \(x\neq y\) 时，在 DFN 序的 \([x - 1,y]\) 区间内寻找 DFN 序最小的一个节点；
当 \(x=y\) 时，特判。
实现
可用 ST表 实现查询。预处理时间复杂度 \(O(n\log n)\)，查询时间复杂度 \(O(1)\)。
板子-> Luogu P3379 【模板】最近公共祖先（LCA）
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
const int log2n = 19;
vector<int> edge[500010];
int dfn[500010];
int st[log2n + 1][500010];
int cur;
#define min(x, y) (dfn[x] < dfn[y] ? x : y)
void dfs(int u, int fa)
{
dfn[u] = ++cur;
st[0][dfn[u]] = fa;
for (auto v : edge[u])
if (v != fa)
dfs(v, u);
return;
}
int lca(int x, int y)
{
if (x == y)
return x;
x = dfn[x];
y = dfn[y];
if (y < x)
swap(x, y);
int log2xy = log2(y - x++);
return min(st[log2xy][x], st[log2xy][y - (1 << log2xy) + 1]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, root;
cin >> n >> m >> root;
for (int i = 1, x, y; i < n; ++i)
cin >> x >> y, edge[x].push_back(y), edge[y].push_back(x);
dfs(root, -1);
for (int i = 1; i <= log2n; ++i)
for (int j = 1; j + (1 << i) - 1 <= n; ++j)
st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
while (m--)
{
int u, v;
cin >> u >> v;
cout << lca(u, v) << "\n";
}
return 0;
}
码风丑陋，敬请谅解