LCA，全称 Least Common Ancestor，是指一棵有根树上的两个点的最近公共祖先。它有很多种求法，不同的求法各有所长，下面是一些常用求法的总结。

倍增

暴力

首先求出每个节点的深度 $dep_u$。

如果我们要求 $u$ 和 $v$ 的 LCA（钦定 $dep_u > dep_v$），最直接的方法就是将 $u$ 往上跳 $dep_u - dep_v$ 次，令两个点深度相等，然后 $u, v$ 一起向上跳，它们第一次相遇的点就是它们的 LCA。

在极端情况下，询问的两个点一个点为叶子，另一个点为根，这种做法的时间复杂度为单次询问 $O(h)$，$h$ 为树高。当树为一条链时，$h = n$。

我们考虑优化跳的过程。

定义一个点的跳 $i$ 次达到的节点为它的 $i$ 级祖先，那么它的 $0$ 级祖先为它本身，它的 $i$ 级祖先为它的 $(i - 1)$ 级祖先的父亲。使用倍增预处理出每个点 $u$ 的 $2^i$ 级祖先，记为 $fa_{u, i}$。如果我们要跳到一个节点的 $k$ 级祖先，只需要 $\log k$ 次跳即可。

然后一起向上跳的部分，我们从 $d = \lfloor \log_2dep_v\rfloor$ 到 $0$ 降序枚举，如果 $fa_{u, d} \not= fa_{v, d}$，就令 $u$ 跳到 $fa_{u, d}$，$v$ 跳到 $fa_{v, d}$。跳完之后，$u$ 和 $v$ 必定只需要跳一步就能相遇，所以 LCA 为 $fa_{u, 0}$。

预处理代码：

void dfs(int u){
	for (int i = G.h(u);i != -1;i = G.E(i).nxt){
		int v = G.E(i).v;
		if (v == fa[0][u]) continue;
		dep[v] = dep[u] + 1, fa[0][v] = u;
		for (int j = 1;fa[j - 1][v];j ++) fa[j][v] = fa[j - 1][fa[j - 1][v]];
		dfs(v);
	}
}

查询代码：

int lca(int a, int b){
	if (dep[b] > dep[a]) swap(a, b);
	int depc = dep[a] - dep[b];
	for (int i = 0;depc;i ++, depc >>= 1){
		if (depc & 1) a = fa[i][a];
	}
	if (a == b) return a;
	for (int i = 19;i >= 0;i --){
		if (fa[i][a] != fa[i][b]) a = fa[i][a], b = fa[i][b];
	}
	return fa[0][a];
}

重链剖分

把这棵树重链剖分，根据重链剖分的性质，一条从某个点到根的路径上，经过的重链数量不超过 $\log n$，所以我们可以暴力向上跳来求出 LCA。

算法流程：（$fa_u$ 为 $u$ 的父亲，$top_u$ 为 $u$ 所在的重链中的深度最小节点）

1. 如果 $u$ 和 $v$ 在同一条重链上（即 $top_u = top_v$），深度较小的即为答案。

2. 找出 $top_u$ 和 $top_v$ 中深度较浅的那个，设为 $x$，然后让 $x$ 跳到 $fa_{top_x}$。

3. 回到步骤一。

查询代码：

int lca(int u, int v){
	while (top[u] != top[v]){
		if (dep[top[u]] < dep[top[v]]) swap(u, v);
		u = fa[top[u]];
	}
	return dep[u] < dep[v] ? u : v;
}

RMQ

我们考虑把 LCA 转化成 RMQ 问题来处理。如何转化呢？考虑 DFS 序。

假设我们要求 $u$ 和 $v$ 的 LCA。如果 $u = v$，LCA 即为 $u$。否则，钦定 $u$ 在 DFS 序列里出现在 $v$ 前面。

有一个结论：设 $u$ 和 $v$ 的 LCA 为 $d$，那么 DFS 序列上 $u$ 到 $v$ 之间一定不会出现 $d$ 以及 $d$ 的祖先，但是必定会出现 $d$ 的儿子。

证明

根据 DFS 序的性质，一个节点的祖先在 DFS 序中只会出现在这个节点前面。

所以 $d$ 以及 $d$ 的祖先既是 $u$ 的祖先又是 $v$ 的祖先，它们必定会出现在 $u$ 前面，而不是 $u, v$ 之间。

考虑 $d$ 到 $v$ 的路径上 $d$ 的下一个节点 $d'$，这个节点一定会出现在 $u, v$ 之间，并且这个节点是 $d$ 的一个儿子，所以结论得证。

根据这个性质，设 $u$ 的出现位置为 $x$，$v$ 的出现位置为 $y$，$u, v$ 的 LCA 就相当于 DFS 序中第 $x + 1$ 项和第 $y$ 项之间的深度最小的点的父亲。用 ST 表预处理即可。

预处理代码：

int mindep(int x, int y){return dep[x] < dep[y] ? x : y;}
void dfs(int u, int fa){
	f[0][dfn[u] = ++ cnt] = fa;
	for (int i = G.h(u);i != -1;i = G.E(i).nxt){
		int v = G.E(i).v;
		if (v != fa) dep[v] = dep[u] + 1, dfs(v, u);
	}
}
void pre(){
    for (int i = 2;i <= n;i ++) Log2[i] = Log2[i >> 1] + 1;
	for (int i = 1;i <= Log2[n];i ++){
		for (int j = 1;j + (1 << i) - 1 <= n;j ++) f[i][j] = mindep(f[i - 1][j], f[i - 1][j + (1 << i - 1)]);
	}
}

查询代码：

inline int lca(int x, int y){
	if (x == y) return x;
	if (dfn[x] > dfn[y]) swap(x, y);
	int l = dfn[x] + 1, r = dfn[y];
	int k = Log2[r - l + 1];
	return mindep(f[k][l], f[k][r - (1 << k) + 1]);
}

Tarjan

使用 Tarjan 求 LCA 是离线的，需要将所有询问读入然后统一回答，还需要一个并查集维护每个点的祖先。

流程如下：

1. 首先我们将询问当作边存进一个新图里，并初始化并查集（每个点的祖先均为自己）。
2. 然后 DFS 整棵树。
   1. 对于每个 $u$ 的儿子 $v$，递归进入 $v$ 子树。
   2. 对于每个与 $u$ 有一条询问边的节点 $v$，如果 $v$ 被访问过，令 $(u, v)$ 的答案为 $\operatorname{getfa}(v)$。
   3. 令 $fa_v = u$。（回溯）

对每个询问节点 $u$，如果对应的 $v$ 节点也被访问过，那么根据 DFS 的性质，$u, v$ 的 LCA 一定还没回溯，而且 $v$ 到 LCA 的路径上的点（不包括 LCA）都回溯了，所以 $\operatorname{getfa}(v)$ 就等于 LCA。

至于时间复杂度的话，Tarjan 本人证明了，只使用路径压缩的并查集在这个算法中时间复杂度单次查询均摊 $O(\alpha(n))$，并非一般的 $O(\log n)$。

DFS 部分代码：

void dfs(int u){
	fa[u] = u, vis[u] = 1;
	for (int i = G.h(u);i != -1;i = G.E(i).nxt){
		int v = G.E(i).v;
		if (!vis[v]) dfs(v), fa[v] = u;
	}
	for (int i = Q.h(u);i != -1;i = Q.E(i).nxt){
		int v = Q.E(i).v, id = Q.E(i).w;
		if (vis[v]) ans[id] = getfa(v);
	}
}

对比

测试题目为洛谷的 LCA 模板题，数据范围为 $1 \le n, q \le 5 \times 10^5$。link

所有代码使用同一种存图方式，同一种语言提交，均开启 O2 优化并全部使用同一份快读。