【模板】最近公共祖先（LCA）

题目描述

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

输入格式

第一行包含三个正整数 $N,M,S$，分别表示树的结点个数、询问的个数和树根结点的序号。

接下来 $N-1$ 行每行包含两个正整数 $x, y$，表示 $x$ 结点和 $y$ 结点之间有一条直接连接的边（数据保证可以构成树）。

接下来 $M$ 行每行包含两个正整数 $a, b$，表示询问 $a$ 结点和 $b$ 结点的最近公共祖先。

输出格式

输出包含 $M$ 行，每行包含一个正整数，依次为每一个询问的结果。

样例 #1

样例输入 #1

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

样例输出 #1

4
4
1
4
4

提示

对于 $30\%$ 的数据，$N\leq 10$，$M\leq 10$。

对于 $70\%$ 的数据，$N\leq 10000$，$M\leq 10000$。

对于 $100\%$ 的数据，$1 \leq N,M\leq 500000$，$1 \leq x, y,a ,b \leq N$，不保证 $a \neq b$。

样例说明：

该树结构如下：

第一次询问：$2, 4$ 的最近公共祖先，故为 $4$。

第二次询问：$3, 2$ 的最近公共祖先，故为 $4$。

第三次询问：$3, 5$ 的最近公共祖先，故为 $1$。

第四次询问：$1, 2$ 的最近公共祖先，故为 $4$。

第五次询问：$4, 5$ 的最近公共祖先，故为 $4$。

故输出依次为 $4, 4, 1, 4, 4$。

2021/10/4 数据更新 @fstqwq：应要求加了两组数据卡掉了暴力跳。

思路

利用倍增的思想，按1，2，4，8 .... 2的n次，由大往小跳；

预处理deep数组表示节点的深度， f[i][k]数组表示从i号节点往上跳2^k所到达的节点，并再dfs时预处理出

向上跳： 对于每个节点，步数从大往小倒序跳：若从小往大可能会出现悔棋现象；例如5，若从小往大，1，2，4后悔棋，改为1，4；而从大往小则4，1；

具体的，对于a和b节点，设a节点的深度大于b节点；首先将a节点向上跳的和b同层，其公共父节点不会发生改变；若跳跃后a == b说明该点即公共父节点；

同层之后，二者一同向上跳，为防止误判（因为是步数由大向小，且有最小公共父节点的父节点一定是二者的公共父节点（但不是最小的）），跳跃时保证二者不能相等，即跳跃到二者第一次相等的下面一层，如此，找到的即是最小的公共父节点

code

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 500010, M = 2 * N;

int n, m, s;
int h[N], e[M], ne[M], idx;
int deep[N], f[N][20]; //deep存储节点的深度，f[i][j]表示第i个节点向上跳2^j距离所到的节点
int lg[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
 } 

void dfs(int u, int p) // 当前节点和其父节点
{
    deep[u] = deep[p] + 1;
    f[u][0] = p;

    for(int i = 1;i <= lg[deep[u]];i ++) // 因为是向前跳，总要小于u的深度 
        f[u][i] = f[f[u][i - 1]][i - 1]; // key:从u向前跳2^i相当于先跳2^(i-1),再跳2^(i-1)(2^i = 2^i-1 + 2^i-1)

    for(int i = h[u]; i != -1 ;i = ne[i])
    {
        int j = e[i];
        if(j == p) continue; // 无向图有可能重复回去
        dfs(j, u); // 继续向下dfs 
     } 
 } 


int lca(int x, int y)
{
    if(deep[x] < deep[y]) swap(x, y); // 假设x深度大于y 

    while(deep[x] > deep[y])
        x = f[x][lg[deep[x] - deep[y]]]; // 进一步优化，保证不会跳到y之上

    if(x == y) return x;

    for(int i = lg[deep[x]];i >= 0;i --)
        if(f[x][i] != f[y][i]) // 两者一同向上跳且保证二者不相遇 
            x = f[x][i], y = f[y][i];

    return f[x][0];
 } 


int main()
{
    scanf("%d%d%d", &n, &m, &s);
    memset(h, -1, sizeof h);

    for(int i = 1;i < n;i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a);
    }

    // 常数优化：预处理出lg 
    lg[0] = -1; 
    for(int i = 1;i <= n;i ++)
        lg[i] = lg[i >> 1] + 1; // 保证当新增加一位二进制位时才发生变化2,4,8,16.... 

    dfs(s, 0);

    while(m --)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", lca(a, b));
    }

    return 0;
}