（2023GESP八级）洛谷P10113题：用树结构解决员工管理的问题

7个月前 (08-17)比赛题解269

一、问题分析

这道题目描述了一个公司的员工层级关系，可以抽象为一个树形结构，其中0号员工是根节点（老板）。我们需要解决的问题是：给定一组员工，找到能够管理所有这些员工的最低层级的共同上级（即编号最大的最近公共祖先）。

二、树结构基础

在计算机科学中，树是一种重要的数据结构，由节点和边组成，具有以下特点：

有一个特殊的节点称为根节点
每个节点有零个或多个子节点
除了根节点外，每个节点有且只有一个父节点

在本问题中，公司的管理结构正好形成了一棵树，其中每个员工（除老板外）都有一个直接领导（父节点）。

三、最近公共祖先(LCA)算法

最近公共祖先(Lowest Common Ancestor)是指在一棵树中，两个节点的共同祖先中离它们最近的节点。对于多个节点，可以依次计算它们的LCA。

四、解决方案

我们可以采用以下步骤解决这个问题：

预处理每个节点的深度和祖先信息
对于每组查询，找出所有节点的LCA
如果有多个可能的LCA，选择编号最大的那个

五、C++代码实现

以下是完整的C++实现代码，包含详细注释：

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

const int MAXN = 1e5 + 5;
const int LOG = 20; // 足够大的对数级别

vector<int> parent(MAXN); // 存储每个节点的直接领导
vector<int> depth(MAXN);  // 存储每个节点的深度
vector<vector<int>> up(MAXN, vector<int>(LOG)); // 倍增表

// 预处理函数，构建倍增表
void preprocess(int n) {
    // 0号节点是根节点，深度为0，没有父节点
    depth[0] = 0;
    up[0][0] = 0; // 根节点的2^0祖先还是自己
    
    // 预处理其他节点
    for(int i = 1; i < n; ++i) {
        depth[i] = depth[parent[i]] + 1;
        up[i][0] = parent[i]; // 2^0祖先就是直接领导
    }
    
    // 填充倍增表
    for(int j = 1; j < LOG; ++j) {
        for(int i = 0; i < n; ++i) {
            up[i][j] = up[up[i][j-1]][j-1];
        }
    }
}

// 查找两个节点的LCA
int lca(int u, int v) {
    // 确保u是较深的节点
    if(depth[u] < depth[v]) swap(u, v);
    
    // 将u提升到与v相同的深度
    for(int j = LOG-1; j >= 0; --j) {
        if(depth[u] - (1 << j) >= depth[v]) {
            u = up[u][j];
        }
    }
    
    // 如果此时u和v相同，则已经找到LCA
    if(u == v) return u;
    
    // 否则，同时提升u和v直到它们的父节点相同
    for(int j = LOG-1; j >= 0; --j) {
        if(up[u][j] != up[v][j]) {
            u = up[u][j];
            v = up[v][j];
        }
    }
    
    return parent[u];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N;
    
    // 读取每个员工的直接领导
    for(int i = 1; i < N; ++i) {
        cin >> parent[i];
    }
    
    // 预处理倍增表
    preprocess(N);
    
    int Q;
    cin >> Q;
    
    while(Q--) {
        int m;
        cin >> m;
        vector<int> employees(m);
        for(int i = 0; i < m; ++i) {
            cin >> employees[i];
        }
        
        // 找出所有员工的LCA
        int current_lca = employees[0];
        for(int i = 1; i < m; ++i) {
            current_lca = lca(current_lca, employees[i]);
        }
        
        cout << current_lca << "\n";
    }
    
    return 0;
}