题目：P3379 最近公共祖先（LCA）

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先．

输入格式#

第一行包含三个正整数 $N,M,S$ ，分别表示树的结点个数、询问的个数和树根结点的序号．

接下来 $N-1$ 行每行包含两个正整数 $x, y$ ，表示 $x$ 结点和 $y$ 结点之间有一条直接连接的边（数据保证可以构成树）．

接下来 $M$ 行每行包含两个正整数 $a, b$ ，表示询问 $a$ 结点和 $b$ 结点的最近公共祖先．

输出格式#

输出包含 $M$ 行，每行包含一个正整数，依次为每一个询问的结果．

数据范围#

对于 $100\%$ 的数据， $1 \leq N,M\leq 5\times10^5$ ， $1 \leq x, y,a ,b \leq N$ ，不保证 $a \neq b$ ．

分析#

LCA（Lowest Common Ancestor）即树上两个节点 $u,v$ 路径上离根最近的公共节点．

常用方法有：

倍增法（预处理 $O(n\log n)$ ，单次查询 $O(\log n)$ ）
树链剖分（重链剖分）
Tarjan 离线算法

最常用、易实现的是倍增法．

倍增法需要：

预处理每个节点的 $2^k$ 级祖先（即 $fa[u][k]$ 表示 $u$ 的第 $2^k$ 级祖先）．
查询时先将 $u,v$ 跳到同一深度，然后一起向上跳，距离从 $2^{\log n}$ 到 $2^0$ ，如果跳到相同的节点就调回来，下一次少跳一些，直到找到最近公共祖先．

具体实现步骤：

建树与初始化

用邻接表存树．
记录每个节点的深度 $deep[u]$ ．
记录每个节点的父节点 $fa[u][0]$ ．

预处理倍增表

对每个节点 $u$ ， $fa[u][k] = fa[fa[u][k-1]][k-1]$ ．
预处理 $k$ 从 $1$ 到 $\log n$ ．

查询 LCA

若 $u,v$ 深度不同，先将较深的节点向上跳到同一深度．
然后从大到小枚举 $k$ ，若 $fa[u][k] \neq fa[v][k]$ ，则 $u,v$ 同时跳到各自的 $2^k$ 级祖先．
最后 $u$ 和 $v$ 的父节点就是 LCA．

复杂度分析#

预处理： $O(n\log n)$
单次查询： $O(\log n)$

标程#

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 100;

int n, m, s;
vector<int> edge[N];
int deep[N];
int fa[N][23];

// 预处理
void getInfo(int t) {
	// 预处理父节点
	deep[t] = deep[fa[t][0]] + 1;
	// 预处理祖宗节点
	for (int i = 1; i < 23; ++i) 
		fa[t][i] = fa[fa[t][i - 1]][i - 1];

	// 递归处理所有的边
	for (int i = 0; i < edge[t].size(); ++i) {
		int to = edge[t][i];
		if (to == fa[t][0]) continue;
		fa[to][0] = t;
		getInfo(to);
	}
}

// 获得t节点向上跳v格跳到的节点编号
int jump(int t, int v) {
	for (int i = 22; i >= 0; --i) {
		if (v >= (1 << i)) {
			t = fa[t][i];
			v -= (1 << i);
		}
	}
	return t;
}

// 获取节点x和节点y的lca
int lca(int x, int y) {
	// 统一深度
	if (deep[y] > deep[x]) y = jump(y, deep[y] - deep[x]);
	else x = jump(x, deep[x] - deep[y]);
	// 处理x和y是同一支上的，有血缘关系的情况
	if (x == y) return x;

	// 向上跳
	for (int i = 22; i >= 0; --i) {
		if (fa[x][i] == fa[y][i]) continue;
		x = fa[x][i], y = fa[y][i];
	}
	return fa[x][0];
}

int main() {
	cin >> n >> m >> s;
	for (int i = 1; i <= n - 1; ++i) {
		int x, y;
		cin >> x >> y;
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	getInfo(s);
	for (int i = 1; i <= m; ++i) {
		int x, y;
		cin >> x >> y;
		cout << lca(x, y) << endl;
	}
	return 0;
}

cpp