能管理所有人的员工 = 这些人的公共祖先;答案是从 LCA 一直走到根这条链上的最大编号。
某公司有 N 名员工,编号从 0 至 N − 1。其中,除了 0 号员工是老板,其余每名员工都有一个直接领导。我们假设编号为 i 的员工的直接领导是 fᵢ。
该公司有严格的管理制度,每位员工只能受到本人或直接领导或间接领导的管理。具体来说,规定员工 x 可以管理员工 y,当且仅当 x = y,或 x = f_y,或 x 可以管理 f_y。特别地,0 号员工老板只能自我管理,无法由其他任何员工管理。
现在,有一些同事要开展合作,他们希望找到一位同事来主持这场合作,这位同事必须能够管理参与合作的所有同事。如果有多名满足这一条件的员工,他们希望找到编号最大的员工。你能帮帮他们吗?
| 项目 | 说明 |
|---|---|
| 输入第一行 | 一个整数 N,表示员工的数量 |
| 输入第二行 | N − 1 个用空格隔开的正整数,依次为 f₁, f₂, …, f_{N−1} |
| 输入第三行 | 一个整数 Q,表示共有 Q 场合作需要安排 |
| 随后 Q 行 | 每行开头是整数 m(2 ≤ m ≤ N),接着是 m 个员工编号(合法且不重复) |
| 输出 | Q 行,每行一个整数,依次为每场合作的主持人选 |
| 结构保证 | 公司结构合法,不存在任意一名员工是自己直接或间接领导 |
| 样例 | 内容 |
|---|---|
| 输入 #1 | 5 |
| 输出 #1 | 2 |
| 输入 #2 | 7 |
| 输出 #2 | 2 |
fᵢ 就是结点 i 的父亲。x 可以管理 y" 就是 "x 是 y 的祖先(或就是 y 本人)",也就是 "x 出现在 y 到根的这条链上"。m 个人的祖先——这正是"公共祖先"的定义。树形结构公共祖先倍增 LCA链上取最大值迭代 BFS 预处理
| 项目 | 说明 |
|---|---|
| 结点编号 | 0 … N − 1(0 号是老板,即树根) |
| 父子关系 | fᵢ 是 i 的直接领导(父亲) |
| 数据范围 | 3 ≤ N ≤ 10⁵,Q ≤ 100,m ≤ 10⁴ |
| 部分分 | 25% 数据 N ≤ 50;50% 数据 N ≤ 300 |
| 管理定义 | x 管理 y ⟺ x 是 y 的祖先或 y 本身 |
| 求解目标 | 能管理全部参与者的员工中编号最大的那一位 |
| 特别说明 | 0 号老板只受自己管理(即根不能被别人管) |
x 能管理 y ⟺ x 在 y 到根的链上。要同时管住全部 m 个人,x 就必须同时出现在这 m 条链上——这些链的公共部分恰好就是"LCA 到根"这一条链m 个点只要 m − 1 次 LCA 运算fᵢ < i?题目没说领导的编号一定比下属小,比如 f₁ = 2 完全合法。所以建树必须用孩子表 + 从根 BFS,不能"从大到小扫一遍"来推深度O(N log N);每次询问 O(m log N) 求 LCA,再 O(深度) ≤ O(N) 沿链走一遍。Q ≤ 100,总量约 10⁷ 级别样例 1 中 N = 5,第二行 0 0 2 2 依次给出 f₁ = 0、f₂ = 0、f₃ = 2、f₄ = 2。
| 员工 i | 直接领导 fᵢ | 含义 |
|---|---|---|
| 1 | 0 | 1 号直接归老板管 |
| 2 | 0 | 2 号也直接归老板管 |
| 3 | 2 | 3 号的领导是 2 号 |
| 4 | 2 | 4 号的领导也是 2 号 |
把父子关系画出来(箭头方向是"谁管谁"):
0 (老板,根)
+-- 1
+-- 2
+-- 3
+-- 43 的祖先链:3 → 2 → 0
4 的祖先链:4 → 2 → 0
两条链的公共部分:2 → 0
LCA(3, 4) = 2,公共祖先 = {2, 0}
链上编号 2、0 里最大的是 2 ⇒ ✅ 主持人 = 2
先 LCA(2, 3) = 2(2 是 3 的领导)
再 LCA(2, 4) = 2
公共祖先仍是 {2, 0}
链上编号最大的是 2 ⇒ ✅ 主持人 = 2
1 的祖先链:1 → 0
4 的祖先链:4 → 2 → 0
两条链只共享 0 这一个点
LCA(1, 4) = 0,公共祖先 = {0}
链上只有 0 ⇒ ✅ 主持人 = 0
| 合作 | 参与者 | LCA | 公共祖先链 | 主持人(链上最大编号) |
|---|---|---|---|---|
| 1 | 3, 4 | 2 | 2 → 0 | 2 |
| 2 | 2, 3, 4 | 2 | 2 → 0 | 2 |
| 3 | 1, 4 | 0 | 0 | 0 |
max 就完成了。构造一棵小树:0 → 5 → 2 → {1, 3},也就是 f₁ = 2、f₂ = 5、f₃ = 2。注意这里 f₁ = 2 比 1 还大,但结构完全合法。
0
+-- 5
+-- 2
+-- 1
+-- 3| 做法 | 算法给出的结果 | 是否符合题意 |
|---|---|---|
| 只输出 LCA | LCA(1, 3) = 2,输出 2 | 错误 |
| 沿 LCA→根 取最大编号 | 链 2 → 5 → 0,取 max 得 5 | 正确 |
2 号能管:它是 1、3 的共同领导 ✓
5 号能管:5 管着 2,2 管着 1 和 3,传递下去 ✓
0 号当然也能管 ✓
3 号不能管 1 号(3 不是 1 的祖先)✗
候选人 = {2, 5, 0},编号最大的是 5
LCA 只告诉我们"公共祖先链的最低端"
链是 2 → 5 → 0,编号分别是 2、5、0
题目比的是编号大小,与深浅无关
✅ 答案 5
题目只保证"公司结构合法",完全没有保证 fᵢ < i。例如 N = 4,第二行为 2 0 2:f₁ = 2、f₂ = 0、f₃ = 2。
0
+-- 2
+-- 1
+-- 3这里 1 号的领导是 2 号,编号比它自己大。如果你的做法是"for (i = N−1; i ≥ 1; i--) dep[i] = dep[fᵢ] + 1",在这组数据上就会算出错误的深度(因为 dep[2] 还没定就先用了)。
先把孩子表建好:ch[0] = {2},ch[2] = {1, 3}
BFS 顺序:0(深度 0)→ 2(深度 1)→ 1、3(深度 2)
询问 {1, 3}:LCA = 2,公共祖先链 2 → 0
链上最大编号 = 2
✅ 答案 2
i = 3:dep[3] = dep[2] + 1,但 dep[2] 此刻还是 0
i = 1:同样用到还没算好的 dep[2]
深度全乱,LCA 也会算错
❌ 结构合法但编号不单调时必挂
fᵢ < i,就老老实实用孩子表 + 从根 BFS 建树。顺手把 par[0] = 0 设成自己,沿父指针走的时候就不会越界。先求出 m 个点的 LCA,再从 LCA 沿父指针走到根,途中记录编号最大值
求完 LCA 直接输出;或对每个候选员工逐一检查是否管得住所有人
| 方案 | 复杂度 | 结论 |
|---|---|---|
| 倍增 LCA + 链上取 max | O(N log N + Q(m log N + 深度)) | ✅ 正确且快,官方做法 |
| 只输出 LCA | O(N log N + Q·m log N) | ❌ 漏掉"编号最大"这一步 |
| 逐点暴力验证所有人 | O(Q · N · m) | ⚠️ 答案对但接近 10⁹,易超时 |
第一行输入 N;第二行输入 f₁ … f_{N−1}(N − 1 个数);第三行输入 Q;随后 Q 行每行先给 m,再给 m 个员工编号。程序会逐场展示公共祖先链与选出的主持人。
点按钮开始 →
#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; const int LOG = 18; // 2^17 = 131072 > 10^5,够用 int n, q; int par[MAXN], dep[MAXN]; int up[MAXN][LOG]; vector<int> ch[MAXN]; // 孩子表:f_i 可能大于 i,不能"倒着扫" int lca(int a, int b) { if (dep[a] < dep[b]) swap(a, b); int d = dep[a] - dep[b]; for (int j = 0; j < LOG; j++) if ((d >> j) & 1) a = up[a][j]; // 把 a 抬到与 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]; // 再上一级就是 LCA } int main() { scanf("%d", &n); for (int i = 1; i < n; i++) { scanf("%d", &par[i]); ch[par[i]].push_back(i); } par[0] = 0; // 根的父亲指向自己,防越界 queue<int> qu; // 迭代 BFS 定深度,防递归爆栈 qu.push(0); dep[0] = 0; for (int j = 0; j < LOG; j++) up[0][j] = 0; while (!qu.empty()) { int x = qu.front(); qu.pop(); for (int t = 0; t < (int)ch[x].size(); t++) { int y = ch[x][t]; dep[y] = dep[x] + 1; up[y][0] = x; // 2^0 = 1 级祖先就是父亲 qu.push(y); } } for (int j = 1; j < LOG; j++) // 倍增预处理 for (int x = 0; x < n; x++) up[x][j] = up[up[x][j - 1]][j - 1]; scanf("%d", &q); while (q--) { int m; scanf("%d", &m); int L; scanf("%d", &L); // 第一个参与者,先当种子 for (int i = 1; i < m; i++) { int y; scanf("%d", &y); L = lca(L, y); // 边读边合并公共祖先 } int ans = L; // 候选人是 L 到根这一整条链 while (L != 0) { // 沿父指针一路走到根 L = par[L]; if (L > ans) ans = L; // 链上取编号最大值 } printf("%d\n", ans); } return 0; }
fᵢ 可能大于 i);② par[0] = 0 让根的父亲指向自己,沿链走时才能在 0 处安全停下;③ 深度用 BFS 求,别递归(N = 10⁵ 的深链会爆栈);④ 求完 LCA 还要沿链取一遍 max。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
ch[par[i]].push_back(i); | 用孩子表建树 | fᵢ 可能大于 i,不能假设父结点编号更小 |
par[0] = 0; | 根的父亲指向自己 | 沿父指针上溯时在根处安全停下,不会越界 |
up[x][j] = up[up[x][j-1]][j-1]; | 倍增递推 | 2ʲ 级祖先 = 先跳 2^(j−1) 级,再跳 2^(j−1) 级 |
L = lca(L, y); | 边读边合并 | LCA 满足结合律,m 个点只要 m − 1 次运算 |
if (L > ans) ans = L; | 链上取最大 | "编号最大"不是"最近公共祖先" |
fᵢ < i,用倒序循环推深度(遇到 f₁ = 2 这类数据就错);③ 忘记 par[0] = 0,沿链上溯时读到下标 0 以外的垃圾值;④ 用递归 DFS 求深度,N = 10⁵ 的链形树直接爆栈;⑤ LOG 开太小(LOG = 17 时 2¹⁶ = 65536 < 10⁵,深度差抬不上去)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
5 | 2 2 0 | 题面样例 1 |
7 | 2 1 1 1 0 | 题面样例 2(含一组 hack 数据) |
3 | 0 | 只有老板能同时管住 1 号和 2 号 |
4 | 2 | f₁ = 2 比 1 大:必须用孩子表 + BFS 建树 |
6 | 5 5 | 链 2 → 5 → 0:编号最大的是 5,只输出 LCA 会得 2 |
6 | 4 | 长链 0→1→2→3→4→5,链上取 max |
par[0] = 0 设了吗?③ 求完 LCA 有没有沿链取 max?④ LOG 够大吗?⑤ 链上走的时候有没有在 0 处停下?fᵢ < i:反例 N = 4、f = 2 0 2,倒序推深度会用到尚未计算的 dep[2]。par[0] = 0:沿父指针上溯到根后没有"停"的条件,会读到越界或死循环。N = 10⁵ 的链会让栈溢出,请用 BFS。LOG 至少要满足 2^LOG > N,建议取 18。O(N)LOG 层 × N 个点 = O(N log N),约 18 × 10⁵ = 1.8 × 10⁶m 个点做 m − 1 次 LCA,每次 O(log N),共 O(m log N)O(深度) ≤ O(N)Q = 100 场,m ≤ 10⁴,Σm ≤ 10⁶ ⇒ 10⁶ × 17 ≈ 1.7 × 10⁷,再加 100 × 10⁵ 的走链开销倍增表 up[N][18] 用 int 存,约 10⁵ × 18 × 4 B ≈ 7 MB;另有孩子表的边数 O(N)、深度数组与父亲数组各 O(N),整体 O(N log N) 空间很宽裕。
✅ 约 10⁷ 次基础操作,1 秒时限内非常轻松。关键是 Q ≤ 100 这个条件很小,所以"每次询问沿链走一遍"完全承受得起。
// ---------- 倍增 LCA 通用模板(迭代预处理,防爆栈)---------- const int LOG = 18; // 满足 2^LOG > maxN int up[MAXN][LOG], dep[MAXN], par[MAXN]; // ① 用孩子表从根出发 BFS:定深度 + 填 up[x][0] = par[x] // ② for (j = 1; j < LOG; j++) // for (x = 0; x < n; x++) // up[x][j] = up[up[x][j-1]][j-1]; // ③ 求 LCA:先把深的抬到同深度,再从高位到低位一起往上跳 // ---------- 本题额外的一步:LCA -> 根 的链上聚合 ---------- int ans = L, x = L; while (x != 0) { x = par[x]; ans = max(ans, x); } // 链上取编号最大值 // 把思路记住:"能管理所有参与者" == "是所有参与者的公共祖先" // -> 公共祖先构成 LCA 到根的一条链 // -> 题目问什么,就在这条链上聚合什么(max / min / 和 / 个数) // 链上聚合只要 O(深度),配上倍增 LCA 就是 O(log N + 深度) 一次询问
把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。
| 能力点 | 本题怎么用 | 还能迁移到 |
|---|---|---|
| 倍增 LCA | 求出 m 个参与者的公共祖先(最低端) | 树上两点距离、树上路径第 k 大、树上差分 |
| 链上聚合 | 沿 LCA → 根 取编号最大值 | "路径上最值 / 路径和"类询问(配倍增多带一个聚合值) |
| 孩子表建树 | 应对 fᵢ 可能大于 i 的输入 | 任何"只给父亲、不保证编号单调"的树 |
| 增量合并 | 边读边把 m 个点合并成同一个 LCA | 多点的公共祖先、多区间求交类问题 |
if (L > ans) 改成 if (L < ans),注意根 0 也会参与比较。)LCA 的深度 + 1?为什么?(这正是"链上聚合"思想的另一面:链上什么统计都能顺手做出来。)