最近公共祖先 LCA

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int N = 100010;
const int LOG = 20;  // log₂(100000) ≈ 17，开到20够用

vector<int> adj[N];  // 邻接表存树
int depth[N];         // depth[i] = 节点 i 的深度（根为1）
int fa[N][LOG];       // fa[i][j] = 节点 i 的第 2^j 级祖先

// BFS 预处理：计算 depth 和 fa 数组
void bfs_lca(int root) {
    queue<int> q;
    q.push(root);
    depth[root] = 1;  // 根节点深度设为1（方便判断，depth=0表示未访问）

    while (!q.empty()) {
        int u = q.front();
        q.pop();
        // 遍历 u 的所有邻居（子节点）
        for (int v : adj[u]) {
            if (depth[v]) continue;  // 已访问过，跳过（v是u的父节点）
            depth[v] = depth[u] + 1;  // 子节点深度 = 父节点深度 + 1
            fa[v][0] = u;  // v 的第 1 级祖先（2^0=1）就是 u
            // 倍增：预处理 v 的所有 2^j 级祖先
            for (int j = 1; j < LOG; j++) {
                // v 的第 2^j 级祖先 = (v的第 2^(j-1) 级祖先)的第 2^(j-1) 级祖先
                fa[v][j] = fa[ fa[v][j-1] ][j-1];
            }
            q.push(v);
        }
    }
}

// 求节点 a 和 b 的最近公共祖先
int lca(int a, int b) {
    // 第1步：确保 a 是较深的节点（如果 a 比 b 浅就交换）
    if (depth[a] < depth[b]) swap(a, b);

    // 第2步：把 a 向上跳，跳到和 b 同一深度
    // 从大到小枚举 j，利用二进制分解
    for (int j = LOG - 1; j >= 0; j--) {
        // 如果 a 跳 2^j 步后仍然比 b 深（或同样深），就跳
        if (depth[fa[a][j]] >= depth[b])
            a = fa[a][j];  // a 向上跳 2^j 步
    }

    // 特殊情况：如果跳到同一深度后 a==b，说明 b 就是 a 的祖先
    if (a == b) return a;

    // 第3步：a 和 b 同一深度但不是同一个点
    // 一起向上跳，跳到 LCA 的下一层
    for (int j = LOG - 1; j >= 0; j--) {
        if (fa[a][j] != fa[b][j]) {
            // 如果跳 2^j 步后两个节点不同，说明 LCA 还在上面
            a = fa[a][j];  // a 向上跳
            b = fa[b][j];  // b 向上跳
        }
    }
    // 此时 a 和 b 的父节点就是 LCA
    return fa[a][0];
}

int main() {
    int n, q;  // n 个节点，q 次查询
    cin >> n >> q;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);  // 无向树，双向加边
        adj[v].push_back(u);
    }
    bfs_lca(1);  // 以节点1为根，预处理

    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << lca(a, b) << endl;
    }
    return 0;
}