【算法学习笔记】DFN序求LCA（最近公共祖先）

前置知识

• 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++); /* 此处可用预处理实现O(1) */
	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;
}

码风丑陋，敬请谅解