lca.cpp

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 100005;  // 最大节点数
const int LOGN = 20;      // 2^20 > 100000

vector<int> adj[MAXN];
int up[MAXN][LOGN];  // up[u][i] 表示 u 的第 2^i 个祖先
int depth[MAXN];

// DFS 预处理深度和第一层父节点
void dfs(int u, int p, int d) {
    depth[u] = d;
    up[u][0] = p;
    for (int i = 1; i < LOGN; i++) {
        up[u][i] = up[up[u][i - 1]][i - 1];
    }
    for (int v : adj[u]) {
        if (v != p) dfs(v, u, d + 1);
    }
}

// 查询 LCA
int get_lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);

    // 1. 将 u 提升到与 v 同一深度
    for (int i = LOGN - 1; i >= 0; i--) {
        if (depth[u] - (1 << i) >= depth[v]) {
            u = up[u][i];
        }
    }

    if (u == v) return u;

    // 2. 同时向上跳，直到找到 LCA 的下一层
    for (int i = LOGN - 1; i >= 0; i--) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }

    return up[u][0];
}

int main() {
    // 示例：建立简单的树
    int n = 5;  // 节点数
    adj[1].push_back(2);
    adj[2].push_back(1);
    adj[1].push_back(3);
    adj[3].push_back(1);
    adj[2].push_back(4);
    adj[4].push_back(2);
    adj[2].push_back(5);
    adj[5].push_back(2);

    dfs(1, 1, 0);  // 从根节点 1 开始

    cout << "LCA of 4 and 5 is: " << get_lca(4, 5) << endl;  // 输出 2
    cout << "LCA of 4 and 3 is: " << get_lca(4, 3) << endl;  // 输出 1

    return 0;
}