每场合作找一个能管理所有人的主持者,若有多个则取编号最大的。
公司有 N 名员工(编号 0 ~ N−1),0 号是老板,其余每人有直接领导 fᵢ。规定 x 能管理 y 当且仅当 x = y,或 x = f_y,或 x 能管理 f_y(即x 是 y 的祖先或本人)。
每场合作给出若干参与者,要找一位能管理所有参与者的主持者;若有多人满足,选编号最大的那位。
祖先链集合求交树上关系暴力枚举
| 项目 | 说明 |
|---|---|
| 输入 | 第一行 N;第二行 f₁…f_{N−1};第三行 Q;随后 Q 行每行 m 与参与者 |
| 输出 | 每行一个主持人编号 |
| 数据范围 | 3 ≤ N ≤ 300,Q ≤ 100 |
| 管理关系 | x 管理 y ⟺ x 在 y 的祖先链上(含 y 自身) |
| 选择规则 | 所有可行者中取编号最大 |
f₁ = 0、f₂ = 0、f₃ = 2、f₄ = 2。所以:2、3、4 号都直接向 0 号汇报?不——f₃ = 2 表示 3 号的领导是 2 号。
| 员工 | 直接领导 | 完整祖先链(含自己) |
|---|---|---|
| 0 | (老板) | 0 |
| 1 | 0 | 1, 0 |
| 2 | 0 | 2, 0 |
| 3 | 2 | 3, 2, 0 |
| 4 | 2 | 4, 2, 0 |
3 的名单:{3, 2, 0}
4 的名单:{4, 2, 0}
交集:{2, 0}
取编号最大 → 2
输出 2 ✓
2 的名单:{2, 0}
与 {3, 2, 0} 求交 → {2, 0}
再与 {4, 2, 0} 求交 → {2, 0}
取最大 → 2
输出 2 ✓
1 的名单:{1, 0}
4 的名单:{4, 2, 0}
交集:{0}(只有老板)
取最大 → 0
输出 0 ✓
输出 2、2、0 ✓ 与样例一致
N = 7,f = [0, 1, 0, 2, 1, 2]:
| 员工 | 直接领导 | 完整祖先链 |
|---|---|---|
| 0 | — | 0 |
| 1 | 0 | 1, 0 |
| 2 | 1 | 2, 1, 0 |
| 3 | 0 | 3, 0 |
| 4 | 2 | 4, 2, 1, 0 |
| 5 | 1 | 5, 1, 0 |
| 6 | 2 | 6, 2, 1, 0 |
4 的名单:{4, 2, 1, 0}
6 的名单:{6, 2, 1, 0}
交集:{2, 1, 0}
取最大编号 → 2(也是层级最深)
输出 2 ✓
4:{4, 2, 1, 0}
5:{5, 1, 0}
6:{6, 2, 1, 0}
三者交集:{1, 0}
取最大编号 → 1
输出 1 ✓
3:{3, 0}
4:{4, 2, 1, 0}
交集:{0}
→ 0
输出 0 ✓
输出 2、1、1、1、0 ✓ 与样例一致
预处理每人祖先链,每场合作求交集取最大值
先求所有参与者的 LCA,但还要再考虑 LCA 的祖先们
| 方案 | 做法 | 风险 |
|---|---|---|
| 祖先集合求交 | 交集后取 max | 低 |
| 求 LCA | 还需再比较其祖先 | 中(易漏) |
第一行输入 N,第二行输入各员工的领导,第三行输入 Q,随后 Q 行输入参与者。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; int f[305]; bool anc[305][305]; // anc[y][x] = true 表示 x 能管理 y int main() { int N; scanf("%d", &N); f[0] = 0; // 老板自我管理 for (int i = 1; i < N; i++) scanf("%d", &f[i]); // 预处理:对每个员工 y,标记它的所有祖先(含自己) for (int y = 0; y < N; y++) { int cur = y; while (true) { anc[y][cur] = true; if (cur == 0) break; // 走到老板为止 cur = f[cur]; } } int Q; scanf("%d", &Q); while (Q--) { int m; scanf("%d", &m); // 候选集:先取第一位参与者的祖先集合 bool cand[305]; for (int x = 0; x < N; x++) cand[x] = false; for (int j = 0; j < m; j++) { int y; scanf("%d", &y); if (j == 0) { for (int x = 0; x < N; x++) cand[x] = anc[y][x]; } else { for (int x = 0; x < N; x++) if (!anc[y][x]) cand[x] = false; } } // 取编号最大的候选者 for (int x = N - 1; x >= 0; x--) { if (cand[x]) { printf("%d\n", x); break; } } } return 0; }
anc[y][y] = true——本人也能管理自己,所以参与者自己也可能成为主持人(样例 1 第 2 场就是 2 号自己主持)。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
f[0] = 0 | 老板 | 0 号自我管理,向上走就停 |
while (true) { anc[y][cur] = true; if (cur == 0) break; cur = f[cur]; } | 收集祖先链 | 含自己,一直到根 |
cand[x] = anc[y][x](第一个参与者) | 初始化候选 | 交集从第一个人的集合开始 |
if (!anc[y][x]) cand[x] = false; | 求交 | 任何一人管不到的就淘汰 |
for (x = N−1; x >= 0; x--) | 取最大编号 | 从大到小找第一个 |
f_i < i 成立(题目只保证无环,不一定编号递增);④ 输出顺序与输入顺序不一致。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
5 | 2 2 0 | 题面样例 1 |
7 | 2 1 1 1 0 | 题面样例 2 |
3 | 0 | 两人分属不同分支,只能找老板 |
3 | 1 | 2 的上级是 1,1 能同时管住 1 和 2 |
3 | 0 | 老板只能自我管理,无法被别人管理 |
一个 N × N 的布尔表(300 × 300),非常小。
✅ 约 900 万次布尔运算,瞬间完成。本题数据范围小,暴力求交是最省心的解法。
// 树上"谁能管理谁"的通用处理 // 1. 预处理每个点的祖先链(含自己,一直到根) for (int y = 0; y < N; y++) { int cur = y; while (true) { anc[y][cur] = true; if (cur == 0) break; cur = f[cur]; } } // 2. "公共祖先" = 祖先集合的交集 // 求交后取最大值即为答案(本题要求编号最大) // 3. 若题目要求"最深的主持者",则答案就是 LCA // 求 LCA 的暴力写法(沿链上跳,沿链打标记) int lca(int u, int v) { bool on[305] = {false}; for (int x = u; ; x = f[x]) { on[x] = true; if (x == 0) break; } for (int y = v; ; y = f[y]) { if (on[y]) return y; if (y == 0) break; } return 0; } // 注意 f[i] 不一定小于 i,所以不能假设"编号小的层级浅"
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 祖先集合求交 | 公共祖先的完整名单 | 所有"谁能管住一组人"的问题 |
| LCA | 最深的公共祖先 | 树上距离、路径问题 |
| 布尔矩阵预处理 | O(N²) 存关系 | N 较小时的通用做法 |