题意概括

给定一棵包含 $N$ 个节点的有根树，以及 $M$ 次查询。每次查询给出两个节点 $u$ 和 $v$，要求计算它们的最近公共祖先（Lowest Common Ancestor, LCA）。

数据范围:

• 节点数 $N$ 和查询数 $M$ 满足 $1 \le N, M \le 5 \times 10^5$。
• 节点编号从 $1$ 到 $N$。

基础知识

最近公共祖先 (LCA)

在一棵有根树中，节点 $u$ 和节点 $v$ 的最近公共祖先（LCA）是指深度最大（即离根最远）的、同时是 $u$ 和 $v$ 祖先的节点。

倍增法 (Binary Lifting)

倍增法是一种用于高效处理树上路径问题的常用技巧，其解决 LCA 问题的核心思想是预处理出每个节点向上跳 $2^k$ 步所能到达的祖先，从而将“向上跳任意步”这个操作优化到对数时间复杂度。

1. 预处理:

   • 我们使用一个二维数组 f[u][k] 来存储节点 u 的第 $2^k$ 个祖先。
   • f[u][0] 就是 u 的父节点。
   • 可以通过动态规划的思想来填充整个数组。u 的第 $2^k$ 个祖先，就是 u 的第 $2^{k-1}$ 个祖先的第 $2^{k-1}$ 个祖先。状态转移方程为：$$f[u][k] = f[f[u][k-1]][k-1]$$
   • 这个预处理过程可以通过一次深度优先搜索（DFS）来完成。在 DFS 中，我们计算每个节点的深度 dep[u] 和它的直接父节点 f[u][0]。DFS 结束后，再利用上述状态转移方程计算出所有的 f[u][k]。整个预处理的时间复杂度为 $O(N \log N)$。

2. 查询:

   • 要查询 u 和 v 的 LCA，我们首先需要将它们调整到同一深度。假设 dep[u] < dep[v]，我们需要将 v 向上跳 dep[v] - dep[u] 步。这个过程可以利用二进制拆分和预处理好的 f 数组在 $O(\log N)$ 时间内完成。
   • 当 u 和 v 到达同一深度后，如果它们是同一个节点，那么这个节点就是它们的 LCA。
   • 如果不是同一个节点，我们就让 u 和 v 同步向上跳。我们从大到小枚举 k（从 $\log N$ 到 0），只要 f[u][k] 和 f[v][k] 不相同，就说明它们的 LCA 还在更上方，于是我们同时令 u = f[u][k] 和 v = f[v][k]。
   • 当这个过程结束后，u 和 v 会停在 LCA 的正下方一层。因此，最终的 LCA 就是 f[u][0]（或 f[v][0]）。查询过程的时间复杂度为 $O(\log N)$。

C++ 代码实现

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 5e5 + 5;
const int L = 20; // log2(5e5) 约等于 19

int n, m, rt;
vector<int> g[N];
int dep[N];
int f[N][L + 1]; // f[u][k] 表示 u 的第 2^k 个祖先

// DFS 预处理深度和直接父节点
void dfs(int u, int p) {
    dep[u] = dep[p] + 1;
    f[u][0] = p;

    // 预处理 f 数组
    for (int i = 1; i <= L; i++) {
        f[u][i] = f[f[u][i - 1]][i - 1];
    }

    for (int v : g[u]) {
        if (v == p) continue;
        dfs(v, u);
    }
}

// 查询 u 和 v 的 LCA
int lca(int u, int v) {
    // 1. 保证 u 在 v 的上面或同一层
    if (dep[u] > dep[v]) {
        swap(u, v);
    }
    
    // 2. 将 v 跳到和 u 同一层
    for (int i = L; i >= 0; i--) {
        if (dep[f[v][i]] >= dep[u]) {
            v = f[v][i];
        }
    }

    // 3. 如果 u 就是 v，则 u 是 LCA
    if (u == v) {
        return u;
    }

    // 4. 同步向上跳，直到 u 和 v 的父节点相同
    for (int i = L; i >= 0; i--) {
        if (f[u][i] != f[v][i]) {
            u = f[u][i];
            v = f[v][i];
        }
    }
    
    // 5. 返回父节点
    return f[u][0];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> rt;

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    // 从根节点开始预处理
    dfs(rt, 0);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << "\n";
    }

    return 0;
}