虽然很久以前就学了树链剖分的lca方法，但是倍增确实简易了许多。
具体思想非常简单：lca即最近公共祖先。最朴素的方法是对于x和y，先让它们到达同一个深度，然后一个一个点的向上跳（也就是找它的父节点）直到到达同一个点为止。这个方法显然太慢，而我们可以很好的用二进制（倍增）来改进它。
利用倍增的思想，每次不是跳一个，而是2^k，其中k >= 0。当然，我们不能随便跳，不然一下跳到根结点也是「同一个点」。因此在这个算法中，先把两个点跳到同一深度，再每次跳到k最大，而不同的点，最后会刚好在LCA下面的两个字节点，再手动向上跳一个即可。
先用dfs预处理，记录深度dep以及fa[x][k]表示x第2^k的祖先。
这里可以交模版。
我的代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
using namespace std;
const int N = 500005;
int fa[N][21],dep[N];
int n,m,s;
struct edge{
int v,next;
}e[N * 2];
int front[N],cnt = 0;
void AddEdge(int u,int v) {
e[++cnt].v = v;
e[cnt].next = front[u];
front[u] = cnt;
}
void dfs(int x,int fx)
{
dep[x] = dep[fx] + 1;
fa[x][0] = fx;
for (int i = 1;(1<<i) <= dep[x]; i++)
fa[x][i] = fa[fa[x][i - 1]][i - 1];
for(int i = front[x]; i; i = e[i].next)
{
int v = e[i].v;
if(v != fx)
dfs(v,x);
}
}
int lca(int x, int y) {
if(dep[x] > dep[y])
swap(x, y);
for (int i = 20; i >= 0; i--)
{
if (dep[x] <= dep[y] - (1<<i))
y = fa[y][i];
}
if (x == y) return x;
for (int i = 20; i >= 0; i--)
{
if(fa[x][i] == fa[y][i]) continue;
else x = fa[x][i],y = fa[y][i];
}
return fa[x][0];
}
int main()
{
int a,b;
scanf("%d%d%d",&n,&m,&s);
for (int i = 1; i < n; i++)
{
scanf("%d%d", &a, &b);
AddEdge(a,b);
AddEdge(b,a);
}
dfs(s, 0);
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &a, &b);
printf("%d\n", lca(a,b));
}
return 0;
}
吐槽一句，不知为何，我在洛谷上有时红名，有时蓝名。