C++高效实现：倍增法求解最近公共祖先（LCA）算法

题目描述

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

输入格式

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

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

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

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

提示

对于 $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$。

C++代码实现

以下是一个使用倍增法预处理和查询最近公共祖先（LCA）的C++代码：

#include <iostream>
#include <vector>

const int MAXN = 500001;  // 最大结点数
const int MAXLOG = 20;    // log2(MAXN)

std::vector<int> graph[MAXN];   // 存储树的结构
int depth[MAXN];                // 结点的深度
int parent[MAXN][MAXLOG];       // 存储每个结点的2^j祖先

// 预处理函数，用于计算每个结点的深度和祖先
void preprocess(int curr, int prev) {
    depth[curr] = depth[prev] + 1;
    parent[curr][0] = prev;

    for (int i = 1; i < MAXLOG; i++) {
        parent[curr][i] = parent[parent[curr][i - 1]][i - 1];
    }

    for (int next : graph[curr]) {
        if (next != prev) {
            preprocess(next, curr);
        }
    }
}

// 查询函数，用于计算两个结点的最近公共祖先
int lca(int a, int b) {
    if (depth[a] < depth[b]) {
        std::swap(a, b);
    }

    // 将结点a移动到与结点b相同的深度
    for (int i = MAXLOG - 1; i >= 0; i--) {
        if (depth[a] - (1 << i) >= depth[b]) {
            a = parent[a][i];
        }
    }

    // 如果结点a和结点b相同，则直接返回
    if (a == b) {
        return a;
    }

    // 同时向上移动结点a和结点b，直到它们的最近公共祖先
    for (int i = MAXLOG - 1; i >= 0; i--) {
        if (parent[a][i] != parent[b][i]) {
            a = parent[a][i];
            b = parent[b][i];
        }
    }

    return parent[a][0];
}

int main() {
    int n, m, s;
    std::cin >> n >> m >> s;

    for (int i = 0; i < n - 1; i++) {
        int x, y;
        std::cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    depth[0] = -1;  // 根结点的深度为0
    preprocess(s, 0);  // 预处理，计算深度和祖先

    for (int i = 0; i < m; i++) {
        int a, b;
        std::cin >> a >> b;
        std::cout << lca(a, b) << std::endl;
    }

    return 0;
}

代码解析

这段代码使用倍增法预处理和查询最近公共祖先（LCA）。

预处理阶段:
- 使用 graph 数组存储树的结构，depth 数组存储每个节点的深度，parent 数组存储每个节点的祖先信息。
- preprocess 函数使用深度优先搜索（DFS）遍历整棵树，计算每个节点的深度和祖先信息。parent[i][j] 表示节点 i 的第 $2^j$ 个祖先。
查询阶段:
- lca 函数用于查询两个节点的最近公共祖先。
- 首先，将深度较深的节点向上移动到与深度较浅的节点相同的深度。
- 然后，同时向上移动两个节点，直到它们的最近公共祖先。
- 最后，返回最近公共祖先的节点编号。

总结

倍增法是一种高效的求解最近公共祖先（LCA）的算法，其预处理时间复杂度为 $O(N\log N)$，查询时间复杂度为 $O(\log N)$。