一组员工都能被同一人管理，等价于这个人是他们的公共祖先；先求这组点的 LCA，再在根到该 LCA 的路径上取最大编号即可。
OJ: luogu
题目 ID: P10113
难度:普及+/提高
标签:LCA倍增树形结构
日期: 2026-06-20 02:32
题意
公司组织结构是一棵以 0 为根的树：
0号员工是老板- 其余每个员工都有一个直接领导
员工 x 能管理员工 y，当且仅当：
x = y- 或者
x是y的祖先
每次给出一组要合作的员工，要求找一个主持人，使得他能管理这组里的所有人。
如果满足条件的人有很多个，要输出：
- 编号最大的那个
样例树
样例一的树结构是：
digraph G {
0 -> 1;
0 -> 2;
2 -> 3;
2 -> 4;
}
对于员工集合 {3,4}：
- 公共祖先有
2和0 - 其中编号更大的是
2
所以答案是 2。
思路
先看一个最直接的暴力：
cpp
// brute.cpp：直接枚举谁来主持，再暴力判断他是不是所有参与者的祖先。
// 这个做法最贴近题意，但每次查询都要逐个试人，只适合小数据。
#include <bits/stdc++.h>
using namespace std;
int n, q;
vector<int> parent_arr;
bool is_ancestor(int anc, int u) {
while (true) {
if (u == anc) {
return true;
}
if (u == 0) {
break;
}
u = parent_arr[u];
}
return anc == 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
parent_arr.assign(n, 0);
for (int i = 1; i < n; i++) {
cin >> parent_arr[i];
}
cin >> q;
while (q--) {
int m;
cin >> m;
vector<int> people(m);
for (int i = 0; i < m; i++) {
cin >> people[i];
}
int answer = 0;
for (int cand = 0; cand < n; cand++) {
bool ok = true;
for (int i = 0; i < m; i++) {
if (!is_ancestor(cand, people[i])) {
ok = false;
break;
}
}
if (ok) {
answer = max(answer, cand);
}
}
cout << answer << '\n';
}
return 0;
}暴力做法是：
- 枚举谁来当主持人
- 逐个判断他是不是所有参与者的祖先
- 在所有合法人里取编号最大
这个办法很直观，但一次查询最坏要把整棵树都扫一遍。
关键观察有两层。
第一层：
- 能管理所有参与者的人，必须是这组点的公共祖先
第二层：
- 所有公共祖先，恰好就是“这组点的 LCA 到根这条链上的所有点”
因为：
- 最低的那个公共祖先就是这组点的 LCA
- 比它更高的祖先也都能管理所有人
- 而 LCA 以下的人不可能同时管理不同分支上的参与者
所以题目并不是“输出 LCA”，而是：
- 先求出这一组员工的 LCA
- 再在“根到 LCA”的路径上找编号最大的点
第二步也很容易预处理。 设：
path_max_id[u]表示从根走到u这条路径上的最大编号
那么每次查询的答案就是：
path_max_id[lca(这一组人)]
于是整题就变成了标准的倍增 LCA 预处理，再把一组点不断两两合并成一个总 LCA。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 5;
const int LOG = 18;
int n, q;
vector<int> child[MAXN];
int depth_arr[MAXN];
int up[MAXN][LOG];
int path_max_id[MAXN];
void init_tree(int n) {
for (int i = 0; i < n; i++) {
child[i].clear();
depth_arr[i] = 0;
path_max_id[i] = 0;
for (int j = 0; j < LOG; j++) {
up[i][j] = 0;
}
}
}
void build_lca() {
vector<int> st;
st.push_back(0);
while (!st.empty()) {
int u = st.back();
st.pop_back();
for (size_t i = 0; i < child[u].size(); i++) {
int v = child[u][i];
depth_arr[v] = depth_arr[u] + 1;
up[v][0] = u;
path_max_id[v] = max(path_max_id[u], v);
for (int j = 1; j < LOG; j++) {
up[v][j] = up[up[v][j - 1]][j - 1];
}
st.push_back(v);
}
}
}
int kth_ancestor(int u, int k) {
for (int j = 0; j < LOG; j++) {
if (k & (1 << j)) {
u = up[u][j];
}
}
return u;
}
int lca(int a, int b) {
if (depth_arr[a] < depth_arr[b]) {
swap(a, b);
}
a = kth_ancestor(a, depth_arr[a] - depth_arr[b]);
if (a == b) {
return a;
}
for (int j = LOG - 1; j >= 0; j--) {
if (up[a][j] != up[b][j]) {
a = up[a][j];
b = up[b][j];
}
}
return up[a][0];
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
init_tree(n);
for (int i = 1; i < n; i++) {
int f;
cin >> f;
child[f].push_back(i);
}
path_max_id[0] = 0;
build_lca();
cin >> q;
while (q--) {
int m;
cin >> m;
int cur_lca;
cin >> cur_lca;
for (int i = 2; i <= m; i++) {
int x;
cin >> x;
cur_lca = lca(cur_lca, x);
}
// 能主持所有人的员工，等价于“所有参与者公共祖先”。
// 在这些公共祖先里取编号最大值，就是根到 LCA 路径上的最大编号。
cout << path_max_id[cur_lca] << '\n';
}
return 0;
}复杂度
设树有 n 个点，一次查询有 m 个参与者。
- 预处理倍增祖先表：
- 单次两点 LCA：
- 一次查询把
m个点不断合并：
空间复杂度：
总结
这题最容易走偏的地方是：
- 不是“编号最大的公共祖先 = LCA”
LCA 只是“最深的公共祖先”，而题目要的是“编号最大的公共祖先”。
真正正确的转化是：
- 先用 LCA 把“公共祖先集合”压成一条链
- 再用
path_max_id在这条链上取最大编号
所以这是一道：
倍增 LCA- 加一个很自然的路径前缀最大值
的组合题。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
