2023年GESP六级工作沟通（洛谷P10109）：LCA问题实战解析

一、问题理解与建模

这道题目将公司层级关系抽象为树结构，每个员工是树中的一个节点，直接领导关系构成父子关系。我们需要解决的问题是：给定一组员工，找到能够管理所有这些员工的最低层级领导（即编号最大的最近公共祖先）。

二、算法核心：LCA的二进制提升法

二进制提升法是一种高效的LCA查询算法，主要分为两个阶段：

1. 预处理阶段：

• 计算每个节点向上2^k层的祖先

• 使用动态规划填充二维数组up[i][k]

2. 查询阶段：

• 先将两个节点提升到同一深度

• 然后同时向上提升直到找到共同祖先

三、实现详解

1. 数据预处理：

• 构建树结构并存储每个节点的子节点

• 使用DFS计算每个节点的深度

• 预处理每个节点的2^k级祖先

2. LCA查询：

• lift函数将节点提升到指定深度

• lca函数实现两个节点的LCA查询

3. 多节点处理：

• 将多个节点的LCA问题转化为连续的成对LCA查询

• 初始LCA设为第一个节点，然后依次与其他节点求LCA

四、完整代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespACe std;

const int MAXN = 1e5 + 5;
const int LOG = 20;

vector<int> parent(MAXN);
vector<vector<int>> up(MAXN, vector<int>(LOG));
vector<int> depth(MAXN);

// 预处理每个节点的2^k级祖先
void preprocess(int n) {
    up[0][0] = 0; // 老板的父节点是自己
    for(int i = 1; i < n; ++i) {
        up[i][0] = parent[i];
    }
    
    for(int k = 1; k < LOG; ++k) {
        for(int i = 0; i < n; ++i) {
            up[i][k] = up[up[i][k-1]][k-1];
        }
    }
}

// 计算节点u的深度
void dfs(int u, int p, const vector<vector<int>>& children) {
    for(int v : children[u]) {
        if(v != p) {
            depth[v] = depth[u] + 1;
            dfs(v, u, children);
        }
    }
}

// 提升节点u到指定深度
int lift(int u, int target_depth) {
    for(int k = LOG-1; k >= 0; --k) {
        if(depth[u] - (1 << k) >= target_depth) {
            u = up[u][k];
        }
    }
    return u;
}

// 查找两个节点的LCA
int lca(int u, int v) {
    if(depth[u] < depth[v]) swap(u, v);
    u = lift(u, depth[v]);
    
    if(u == v) return u;
    
    for(int k = LOG-1; k >= 0; --k) {
        if(up[u][k] != up[v][k]) {
            u = up[u][k];
            v = up[v][k];
        }
    }
    return parent[u];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    
    vector<vector<int>> children(N);
    parent[0] = 0;
    for(int i = 1; i < N; ++i) {
        cin >> parent[i];
        children[parent[i]].push_back(i);
    }
    
    // 预处理
    preprocess(N);
    depth[0] = 0;
    dfs(0, -1, children);
    
    int Q;
    cin >> Q;
    while(Q--) {
        int m;
        cin >> m;
        vector<int> group(m);
        for(int i = 0; i < m; ++i) {
            cin >> group[i];
        }
        
        // 找到所有节点的LCA
        int current_lca = group[0];
        for(int i = 1; i < m; ++i) {
            current_lca = lca(current_lca, group[i]);
            if(current_lca == 0) break; // 已经到根节点
        }
        
        cout << current_lca << '\n';
    }
    
    return 0;
}