一、问题理解与建模
这道题目将公司层级关系抽象为树结构，每个员工是树中的一个节点，直接领导关系构成父子关系。我们需要解决的问题是：给定一组员工，找到能够管理所有这些员工的最低层级领导（即编号最大的最近公共祖先）。
二、算法核心：LCA的二进制提升法
二进制提升法是一种高效的LCA查询算法，主要分为两个阶段：
三、实现详解
- 数据预处理：
- 构建树结构并存储每个节点的子节点
- 使用DFS计算每个节点的深度
- 预处理每个节点的2^k级祖先
- LCA查询：
lift函数将节点提升到指定深度lca函数实现两个节点的LCA查询
- 多节点处理：
- 将多个节点的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;
}
