公共祖先： 在一棵有根树上，若节点 \(F\) 是节点 \(x\) 的祖先，也是节点 \(y\) 的祖先，那么称 \(F\) 是 \(x\) 和 \(y\) 的公共祖先。
最近公共祖先（LCA）： 在 \(x\) 和 \(y\) 的所有公共祖先中，深度最大的称为最近公共祖先，记为 \(LCA(x,y)\)。
LCA 显然有以下性质。
- 在所有公共祖先中，\(LCA(x,y)\) 到 \(x\) 和 \(y\) 的距离都是最短的。例如，在 \(e\) 和 \(g\) 的所有祖先中，\(c\) 距离更短。
- \(x\) 与 \(y\) 之间最短的路径经过 \(LCA(x,y)\)。例如，从 \(e\) 到 \(g\) 的最短路径经过 \(c\)。
- \(x\) 和 \(y\) 本身也可以是它们自己的公共祖先。若 \(y\) 是 \(x\) 的祖先，则有 \(LCA(x,y)=y\)，如图中 \(d=lca(d,h)\)。
如何求 LCA？根据 LCA 的定义，很容易想到一个简单直接的方法：分别从 \(x\) 和 \(y\) 出发，一直向根节点走，第一次相遇的节点就是 \(LCA(x,y)\)。具体实现时，可以用标记法：首先从 \(x\) 出发一直向根节点走，沿路标记所有经过的祖先节点；把 \(x\) 的祖先标记完之后，然后再从 \(y\) 出发向根节点走，走到第一个被 \(x\) 标记的节点，就是 \(LCA(x,y)\)。标记法的时间复杂度较高，在有 \(n\) 个节点的树上求一次 \(LCA(x,y)\) 的时间复杂度为 \(O(n)\)。若有 \(m\) 次查询，总的时间复杂度为 \(O(mn)\)，效率太低。
倍增法求 LCA
可以把标记法换一种方式实现，分为以下两个步骤。
- 先把 \(x\) 和 \(y\) 提到相同的深度。例如，\(x\) 比 \(y\) 深，就把 \(x\) 提到 \(y\) 的高度（既让 \(x\) 走到 \(y\) 的同一高度），如果发现 \(x\) 直接就跳到 \(y\) 的位置上了，那么就停止查找，否则继续下一步。
- 让 \(x\) 和 \(y\) 继续同步向上走，每走一步就判断是否相遇，相遇点就是 \(LCA(x,y)\) 停止。
上面的两个步骤，如果 \(x\) 和 \(y\) 都一步一步向上走，时间复杂度为 \(O(n)\)。如何改进？如果不是一步步走，而是跳着走，就能加快速度。如何跳？可以按 \(2\) 的倍数向上跳，即跳 \(1,2,4,8,\cdots\) 步，这就是倍增法，倍增法用“跳”的方法加快了上述两个步骤。
步骤 1
把 \(x\) 和 \(y\) 提到相同的深度。具体任务是：给定两个节点 \(x\) 和 \(y\)，设 \(x\) 比 \(y\) 深，让 \(x\) “跳”到与 \(y\) 相同的深度。
因为已知条件是只知道每个节点的父节点，所以如果没有其他辅助条件，\(x\) 只能一步步向上走，没法“跳”。要实现“跳”的动作，必须提前计算出一些 \(x\) 的祖先节点，作为 \(x\) 的“跳板”。然而，应该提前计算出哪些祖先节点呢？如何通过这些预计算出的节点准确且高效地跳到一个任意给定的 \(y\) 的深度？这就是倍增法的精妙之处：预计算出每个节点的第 \(1,2,4,8,16,\cdots\) 个祖先，即按 \(2\) 倍增的那些祖先。
有了预计算出的这些祖先做跳板，能从 \(x\) 快速跳到任何一个给定的目标深度。以从 \(x\) 跳到它的第 \(27\) 个祖先为例：
- 从 \(x\) 跳 \(16\) 步，到达 \(x\) 的第 \(16\) 个祖先 \(fa_1\)；
- 从 \(fa_1\) 跳 \(8\) 步，到达 \(fa_1\) 的第 \(8\) 个祖先 \(fa_2\)；
- 从 \(fa_2\) 跳 \(2\) 步到达祖先 \(fa_3\)；
- 从 \(fa_3\) 跳 \(1\) 步到达祖先 \(fa_4\)。
共跳了 \(16+8+2+1=27\) 步，这个方法利用了二进制的特征：任何一个数都可以由 \(2\) 的倍数相加得到。\(27\) 的二进制是 \(11011\)，其中的 \(4\) 个 \(1\) 的权值就是 \(16,8,2,1\)。
显然，用倍增法从 \(x\) 跳到某个 \(y\) 的时间复杂度为 \(O(\log n)\)。
剩下的问题是如何快速预计算每个节点的“倍增”的祖先。定义 \(fa_{x,i}\) 为 \(x\) 的第 \(2^i\) 个祖先，有非常巧妙的递推关系：\(fa_{x,i}=fa_{fa_{x,i-1},i-1}\)。分两步理解：\(fa_{x,i-1}\) 从 \(x\) 起跳，先跳 \(2^{i-1}\) 步，记这个点为 \(z\)；再从 \(z\) 跳 \(2^{i-1}\) 步，一共跳了 \(2^{i-1}+2^{i-1}=2^i\) 步。
特别地，\(fa_{x,0}\) 是 \(x\) 的第 \(2^0=1\) 个祖先，就是 \(x\) 的父节点。\(fa_{x,0}\) 是递推式的初始条件，从它开始递推出了所有的 \(fa_{x,i}\)。递推的计算量有多大？从任意节点 \(x\) 到根节点，最多只有 \(\log n\) 个祖先，所以只需要递推 \(O(\log n)\) 次。所以整个 \(fa\) 的计算时间复杂度为 \(O(n \log n)\)。
步骤 2
经过上一个步骤，\(x\) 和 \(y\) 现在位于同一深度，让它们同步向上跳，就能找到它们的公共祖先。\(x\) 和 \(y\) 的公共祖先有很多，LCA(x, y) 是距离 \(x\) 和 \(y\) 最近的那个，其他祖先都更远。
从一个节点跳到根节点，最多跳 \(\log n\) 次。现在从 \(x,y\) 出发，从最大的 \(i \approx \log n\) 开始，跳 \(2^i\) 步，分别跳到 \(fa_{x,i},fa_{y,i}\)，它们位于非常靠近根节点的位置（\(2^i \approx n\)），有以下两种情况：
- \(fa_{x,i}=fa_{y,i}\)，这是一个公共祖先，它的深度小于或等于 LCA(x, y)，这说明跳过头了，退回去换一个小的 \(i-1\) 重新跳一次。
- \(fa_{x,i} \ne fa_{y,i}\)，说明还没跳到公共祖先，那么更新 \(x \leftarrow fa_{x,i}, y \leftarrow fa_{y,i}\)，从新的起点 \(x,y\) 继续开始跳。由于新的 \(x,y\) 的深度比原来位置的深度减少超过一半，再跳时就不用跳 \(2^i\) 步，跳 \(2^{i-1}\) 步就够了。
以上两种情况，分别是比 LCA(x, y) 浅和深的两种位置。用 \(i\) 循环判断以上两种情况，就是从深浅两侧逐渐逼近 LCA(x, y)。每循环一次，\(i\) 减一，当 \(i\) 减为 \(0\) 时，\(x\) 和 \(y\) 正好位于 LCA(x,y) 的下一层，则 \(fa_{x,0}\) 就是 LCA(x,y)。
查询一次 LCA 的时间复杂度是多少？这里的 \(i\) 会从 \(\log n\) 递减到 \(0\)，循环 \(O(\log n)\) 次。
倍增法的总计算量包括预计算 \(fa\) 和查询 \(m\) 次 LCA，总时间复杂度为 \(O(n \log n + m \log n)\)。
例题：P3379 【模板】最近公共祖先（LCA）
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 500005;
const int LOG = 19;
vector<int> tree[N];
int depth[N], fa[N][LOG];
void dfs(int cur, int pre) {
depth[cur] = depth[pre] + 1; // 深度比父节点深度多1
for (int nxt : tree[cur]) { // 遍历所有邻居节点
if (nxt != pre) { // 除了父节点以外都是子节点
fa[nxt][0] = cur; // 记录父节点fa[][0]
dfs(nxt, cur);
}
}
}
int lca(int x, int y) {
if (depth[x] < depth[y]) swap(x, y); // 保证x深度更大
// 将x和y提到相同高度
int delta = depth[x] - depth[y];
for (int i = LOG - 1; i >= 0; i--)
if (delta & (1 << i)) x = fa[x][i];
if (x == y) return x; // 如果提到相同深度后已经重合，则直接返回
// x和y同步往上跳
for (int i = LOG - 1; i >= 0; i--)
if (fa[x][i] != fa[y][i]) { // 如果祖先相等，说明跳过头了，换一个小的i继续尝试
x = fa[x][i]; y = fa[y][i]; // 如果祖先不相等，就更新x和y继续跳
}
// 最终x和y位于LCA的下一层，此时x或y的父节点就是LCA
return fa[x][0];
}
int main()
{
int n, m, s; scanf("%d%d%d", &n, &m, &s);
for (int i = 1; i < n; i++) {
int x, y; scanf("%d%d", &x, &y);
// 建树
tree[x].push_back(y); tree[y].push_back(x);
}
dfs(s, 0); // 预处理深度等信息
for (int i = 1; i < LOG; i++)
for (int j = 1; j <= n; j++)
fa[j][i] = fa[fa[j][i - 1]][i - 1]; // 从fa[][0]开始递推
while (m--) {
int a, b; scanf("%d%d", &a, &b); printf("%d\n", lca(a, b));
}
return 0;
}
例题：P4180 [BJWC2010] 严格次小生成树
#include <cstdio>
#include <algorithm>
#include <vector>
using std::sort;
using std::swap;
using std::min;
using std::max;
using std::vector;
typedef long long LL;
const int N = 1e5 + 5;
const int M = 3e5 + 5;
const int LOG = 17;
const LL INF = 1e15;
struct Edge {
int x, y, z;
};
Edge edges[M];
bool mst[M];
vector<Edge> tree[N];
int root[N], depth[N], fa[N][LOG], w1[N][LOG], w2[N][LOG];
int query(int x) {
return root[x] == x ? x : root[x] = query(root[x]);
}
void update(int& mx1, int& mx2, int a1, int a2, int b1, int b2) {
mx1 = max(a1, b1);
mx2 = a1 == b1 ? max(a2, b2) : max(min(a1, b1), max(a2, b2));
}
void dfs(int u, int pre) {
depth[u] = depth[pre] + 1;
fa[u][0] = pre;
for (Edge e : tree[u]) {
int v = e.y, w = e.z;
if (v == pre) continue;
w1[v][0] = w;
dfs(v, u);
}
}
LL lca(int x, int y, int w, LL sum) {
if (depth[x] < depth[y]) swap(x, y);
int delta = depth[x] - depth[y];
int res1 = 0, res2 = 0;
for (int i = LOG - 1; i >= 0; i--)
if (delta & (1 << i)) {
update(res1, res2, res1, res2, w1[x][i], w2[x][i]);
x = fa[x][i];
}
if (x == y) {
return w == res1 ? (res2 == 0 ? INF : sum + w - res2) : (res1 == 0 ? INF : sum + w - res1);
}
int tmp1 = 0, tmp2 = 0;
for (int i = LOG - 1; i >= 0; i--)
if (fa[x][i] != fa[y][i]) {
update(tmp1, tmp2, w1[x][i], w2[x][i], w1[y][i], w2[y][i]);
update(res1, res2, res1, res2, tmp1, tmp2);
x = fa[x][i]; y = fa[y][i];
}
update(tmp1, tmp2, w1[x][0], w2[x][0], w1[y][0], w2[y][0]);
update(res1, res2, res1, res2, tmp1, tmp2);
return w == res1 ? (res2 == 0 ? INF : sum + w - res2) : (res1 == 0 ? INF : sum + w - res1);
}
int main()
{
int n, m; scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) root[i] = i;
for (int i = 1; i <= m; i++) {
scanf("%d%d%d", &edges[i].x, &edges[i].y, &edges[i].z);
}
sort(edges + 1, edges + m + 1, [](Edge& e1, Edge& e2) {
return e1.z < e2.z;
});
LL sum = 0;
for (int i = 1; i <= m; i++) {
int x = edges[i].x, y = edges[i].y, z = edges[i].z;
int qx = query(x), qy = query(y);
if (qx != qy) {
root[qx] = qy; sum += z; mst[i] = true;
tree[x].push_back({x, y, z});
tree[y].push_back({y, x, z});
}
}
dfs(1, 0);
for (int i = 1; i < LOG; i++)
for (int j = 1; j <= n; j++) {
fa[j][i] = fa[fa[j][i - 1]][i - 1];
int a1 = w1[j][i - 1], a2 = w2[j][i - 1];
int b1 = w1[fa[j][i - 1]][i - 1], b2 = w2[fa[j][i - 1]][i - 1];
update(w1[j][i], w2[j][i], a1, a2, b1, b2);
}
LL ans = INF;
for (int i = 1; i <= m; i++) {
int x = edges[i].x, y = edges[i].y, z = edges[i].z;
if (x == y) continue;
if (!mst[i]) ans = min(ans, lca(x, y, z, sum));
}
printf("%lld\n", ans);
return 0;
}