利用倍增的思想实现LCA算法

前言

LCA算法指的是最近公共祖先（Lowest Common Ancestor），这里的最近指的是给定的两个点中所有的公共祖先中，距离根节点最远的节点，而且这两点到最近公共祖先的距离只和也是这两点之间的最短路径。

实现

实现该算法一般是借助每个节点的深度信息进行求解，具体为：

假设要求x和y的LCA ，不妨假设depth[x] > depth[y]，我们先让x往上跳（朝着根的方向），直到二者的深度相同，然后x和y同时网上跳，最终二者一定会在某一点相遇，这点就是所求。

这也叫朴素实现方法，当一棵树深度很大，查询点都是比较深的时候，此时在网上跳的过程会花费大量的时间，时间复杂度是O(n)。

而倍增思想解决的是，优化向上跳转的过程，每次尽可能地往上跳更多的距离。

相关代码说明请看代码注释：

/*
 * @Author      : YaleXin
 * @Email       : me@yalexin.top
 * @LastEditors : YaleXin
 */
#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
// const int MAX_N = 5e5 + 1, MAX_M = 5e5 + 1;
const int MAX_N = 5e2 + 1, MAX_M = 5e2 + 1;
struct Edge{
    int v, next;
}edges[MAX_M << 1];
// head[] 节点i的第一条边，depth[] 节点的深度, f[][] 第i号节点的第2^j个祖先
int head[MAX_N], edgeNum = 1, depth[MAX_N], f[MAX_N][22], n;
// 预处理 log2(i) 向下取整的值
int lg2[MAX_N];
void preLg2(){
    lg2[2] = 1;
    for(int i = 3; i <= n; ++i) 
	  lg2[i] = lg2[i - 1] + (2 << lg2[i - 1] == i);
}
// 采用链式前向星方式模拟链表
inline void add(int u, int v){
    edges[edgeNum].v = v, edges[edgeNum].next = head[u];
    head[u] = edgeNum++;
}
// 快速读入，可理解为 scanf()
inline int read(){
    int sum = 0;
    char ch = getchar();
    while (ch < '0'  || ch > '9')ch = getchar();
    while (ch <= '9' && ch >= '0'){
        sum = (sum << 1)  + (sum << 3) + ch - '0';
        ch = getchar();
    }
    return sum;
}
void dfs(int nowId, int fa){
    // 第 2 ^ 0 即第一个祖先（从 nowId 往根节点方向）
    f[nowId][0] = fa;
    depth[nowId] = depth[fa] + 1;

    for (int i = 1; i <= lg2[depth[nowId]]; i++)
        // nowId 的第 2 ^ i 祖先是它的第 2 ^ (i - 1)个祖先的第 2 ^ (i - 1)个祖先
        // 要画图才能理解
        f[nowId][i] = f[f[nowId][i - 1]][i - 1];

    for (int eId = head[nowId]; eId; eId = edges[eId].next)
        if (edges[eId].v != fa)dfs(edges[eId].v, nowId);
}
int lca(int x, int y){
    if (depth[x] < depth[y])swap(x, y);
    // 目的是将二者处理到同一个高度
    while (depth[x] > depth[y])
        // 以高度差为依据进行跳
        x = f[x][lg2[depth[x] - depth[y]]];
    // 二者相等，毫无疑问，此时 x 就是 y 的祖先
    if(x == y)return x;
    for (int step = lg2[depth[x]];step >= 0; step--)
        if (f[x][step] != f[y][step])
            x = f[x][step], y = f[y][step];
    return f[x][0];
}
int main(){
    n = read();
    int m = read(), s = read(), u, v;
    for(int i = 1; i < n; i++){
        u = read(), v = read();
        add(u, v), add(v, u);
    }
    preLg2();
    dfs(s, 0);
    for (int i = 1; i <= m; i++){
        u = read(), v = read();
        printf("%d\n", lca(u, v));
    }
    return 0;
}
/*


5 5 4
3 1
2 4
5 1
1 4

2 4
3 2
3 5
1 2
4 5


*/

题目参考：洛谷P3397