目录
倍增法求 LCA
倍增法
倍增法（英语：binary lifting），顾名思义就是翻倍。它能够使线性的处理转化为对数级的处理，大大地优化时间复杂度。
这个方法在很多算法中均有应用，其中最常用的是 RMQ 问题和求 LCA（最近公共祖先）。
实现
'f[x][i]' 表示 x 向上跳 \(2^i\) 步到达的结点编号。
$\huge{点我查看代码}$
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int f[500001][20];
int dep[500001];
int maxL;
const int N = 500001;
struct edge
{
int to, nxt; // w是边长
}e[N*2];
int cnt, head[N];
void add(int x, int y)
{
e[++cnt] = (edge){y, head[x]};
head[x] = cnt;
}
void dfs(int x, int fa)
{
dep[x] = dep[fa]+1;
f[x][0] = fa;
for(int i = 1;(1<<i) <= dep[x];i++)
{
f[x][i] = f[f[x][i-1]][i-1];
maxL = max(i, maxL);
}
for(int i = head[x];i;i = e[i].nxt)
{
int y = e[i].to;
if(y == fa) continue;
dfs(y,x);
}
}
int lca(int x, int y)
{
if(dep[x] < dep[y]) swap(x,y);
for(int i = maxL;i >= 0;i--)
if(dep[x] - dep[y] >= (1<<i))
x = f[x][i];
if(x == y) return x;
// 深度更大的点向上走，直到两点深度相同
for(int i = maxL;i >= 0;i--)
if(f[x][i] != f[y][i])
x = f[x][i], y = f[y][i];
// 两点同时向上走，走到重合时停止
return f[x][0];
// 返回f[x][0];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, m, s;
cin >> n >> m >> s;
for(int i = 1;i < n;i++)
{
int x, y;
cin >> x >> y;
add(x, y);
add(y, x);
}
dfs(s,s);
for(int i = 1;i <= m;i++)
{
int a, b;
cin >> a >> b;
cout << lca(a, b) << "\n";
}
return 0;
}