GESP 题解库 / 8 级题解 / [GESP202312 八级] 大量的工作沟通 · 第 19 / 24 题
GESP202312 八级 · P10113 · 中等

大量的工作沟通

能管理所有人的员工 = 这些人的公共祖先;答案是从 LCA 一直走到根这条链上的最大编号。

🌳
N ≤ 10⁵
员工数(0 号是根)
🔍
Q ≤ 100
合作场次(m ≤ 10⁴)
⚡
O(m log N + 深度)
单次询问
🎯
倍增 LCA + 链上取最大
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

某公司有 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 行,每行一个整数,依次为每场合作的主持人选
结构保证公司结构合法,不存在任意一名员工是自己直接或间接领导

输入输出样例

样例内容
输入 #15
0 0 2 2
3
2 3 4
3 2 3 4
2 1 4
输出 #12
2
0
输入 #27
0 1 0 2 1 2
5
2 4 6
2 4 5
3 4 5 6
4 2 4 5 6
2 3 4
输出 #22
1
1
1
0
💡
人话翻译:把公司看成一棵以 0 号为根的树,fᵢ 就是结点 i 的父亲。
"x 可以管理 y" 就是 "x 是 y 的祖先(或就是 y 本人)",也就是 "x 出现在 y 到根的这条链上"。
于是一场合作要找的员工,必须同时是这 m 个人的祖先——这正是"公共祖先"的定义。
关键在于:公共祖先不止一个!它们是"最近公共祖先 LCA 一直到根"这一整条链上的所有点。
而题目要的是这条链上编号最大的那个——注意它未必就是 LCA 本身。

🔍 关键词提取

树形结构公共祖先倍增 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 号老板只受自己管理(即根不能被别人管)

需要解决的问题

02
思维导图
整理解题思路的全貌
🌳 倍增 LCA + 沿 LCA→根 取编号最大
🧠 问题转化
能管理所有人 ⟺ 公共祖先
公共祖先集合 = LCA 到根的整条链
答案 = 这条链上的最大编号
不一定等于 LCA 本身
🌲 建树
fᵢ 是结点 i 的父亲
fᵢ 可能比 i 大 ⇒ 必须用孩子表
从根 0 出发 BFS 定深度
根的父亲记为自己,防越界
⚡ 倍增 LCA
up[x][j]:x 的第 2ʲ 级祖先
先把深的结点抬到同一深度
再从高位到低位一起往上跳
第一个跳不动的位置的上方即 LCA
⚠️ 易错点
只输出 LCA,忘了链上取 max
用"父亲编号一定更小"的错误假设
递归 DFS 求深度会爆栈
lca 与 par 的数组下标越界
03
样例手算推导
样例 1 的三场合作逐一手算 + 一个"编号最大 ≠ LCA"的陷阱例子

🧮 样例 1:先看清这棵"公司树"

样例 1 中 N = 5,第二行 0 0 2 2 依次给出 f₁ = 0、f₂ = 0、f₃ = 2、f₄ = 2。

员工 i直接领导 fᵢ含义
101 号直接归老板管
202 号也直接归老板管
323 号的领导是 2 号
424 号的领导也是 2 号

把父子关系画出来(箭头方向是"谁管谁"):

0  (老板,根)
+-- 1
+-- 2
    +-- 3
    +-- 4
1
合作 1:参与者 {3, 4}

3 的祖先链:3 → 2 → 0

4 的祖先链:4 → 2 → 0

两条链的公共部分:2 → 0

LCA(3, 4) = 2,公共祖先 = {2, 0}

链上编号 2、0 里最大的是 2 ⇒ ✅ 主持人 = 2

2
合作 2:参与者 {2, 3, 4}

先 LCA(2, 3) = 2(2 是 3 的领导)

再 LCA(2, 4) = 2

公共祖先仍是 {2, 0}

链上编号最大的是 2 ⇒ ✅ 主持人 = 2

3
合作 3:参与者 {1, 4}

1 的祖先链:1 → 0

4 的祖先链:4 → 2 → 0

两条链只共享 0 这一个点

LCA(1, 4) = 0,公共祖先 = {0}

链上只有 0 ⇒ ✅ 主持人 = 0

📊 三场合作的答案

合作参与者LCA公共祖先链主持人(链上最大编号)
13, 422 → 02
22, 3, 422 → 02
31, 4000
🔑
把"公共祖先"想成一条链:LCA 是这条链的最低端,根是最高端,中间每一层都在链上,它们全都能管住所有参与者。
所以题目问的其实是"在这条链上挑一个编号最大的",沿父指针从 LCA 一路走到根、顺手记一个 max 就完成了。

🧮 必须看懂的陷阱:编号最大 ≠ 最近的公共祖先

构造一棵小树:0 → 5 → 2 → {1, 3},也就是 f₁ = 2、f₂ = 5、f₃ = 2。注意这里 f₁ = 2 比 1 还大,但结构完全合法。

0
+-- 5
    +-- 2
        +-- 1
        +-- 3
做法算法给出的结果是否符合题意
只输出 LCALCA(1, 3) = 2,输出 2错误
沿 LCA→根 取最大编号链 2 → 5 → 0,取 max 得 5正确
1
谁真的能管住 1 号与 3 号?

2 号能管:它是 1、3 的共同领导 ✓

5 号能管:5 管着 2,2 管着 1 和 3,传递下去 ✓

0 号当然也能管 ✓

3 号不能管 1 号(3 不是 1 的祖先)✗

候选人 = {2, 5, 0},编号最大的是 5

2
于是正确答案是 5,不是 LCA

LCA 只告诉我们"公共祖先链的最低端"

链是 2 → 5 → 0,编号分别是 2、5、0

题目比的是编号大小,与深浅无关

✅ 答案 5

⚠️
这是本题最容易丢分的地方:很多同学求出 LCA 就直接输出,样例 1 恰好能过(因为那道题里链上的编号恰好以 LCA 最大),但上面这个例子会立刻露馅——输出 2,正确答案是 5。
务必记住:"能管理所有人的员工"是一个集合(一条链),不是单点;要求的还是这个集合里的最值。

🧮 第二个陷阱:fᵢ 不一定比 i 小

题目只保证"公司结构合法",完全没有保证 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] 还没定就先用了)。

1
✅ 正确做法:从根 0 出发 BFS

先把孩子表建好:ch[0] = {2},ch[2] = {1, 3}

BFS 顺序:0(深度 0)→ 2(深度 1)→ 1、3(深度 2)

询问 {1, 3}:LCA = 2,公共祖先链 2 → 0

链上最大编号 = 2

✅ 答案 2

2
❌ 错误做法:倒着扫一遍推深度

i = 3:dep[3] = dep[2] + 1,但 dep[2] 此刻还是 0

i = 1:同样用到还没算好的 dep[2]

深度全乱,LCA 也会算错

❌ 结构合法但编号不单调时必挂

🔑
结论:凡是"给出每个点的父亲"的树,只要没有额外保证 fᵢ < i,就老老实实用孩子表 + 从根 BFS 建树。顺手把 par[0] = 0 设成自己,沿父指针走的时候就不会越界。
04
解法对比
倍增 LCA 求链 + 链上取最大 vs 逐点暴力 vs 只输出 LCA

⚔️ 解法对比

🟢 倍增 LCA + 链上取最大(推荐) 推荐

先求出 m 个点的 LCA,再从 LCA 沿父指针走到根,途中记录编号最大值

  • 预处理 O(N log N)
  • 单次询问 O(m log N + 深度)
  • 代码约 60 行
  • 官方题解即此做法
💡
正确性来源:能管理所有人的员工 ⟺ 所有参与者的公共祖先;这些公共祖先恰好是 LCA 到根的一条链。所以在链上取编号最大就是答案,既不会漏也不会多。

🟠 只输出 LCA / 逐点暴力比对

求完 LCA 直接输出;或对每个候选员工逐一检查是否管得住所有人

  • 只输出 LCA:代码最短,但答案错
  • 逐点暴力:单次询问 O(Nm)
  • N = 10⁵、m = 10⁴ 时约 10⁹
  • 常数大,容易超时
⚠️
它们为什么会挂:只输出 LCA 忽略了"编号最大"这一要求(见上面的 0 → 5 → 2 反例);逐点暴力则是把每个候选人都拿去和 m 个点比祖先关系,虽然答案对,但 10⁹ 量级在时限内很危险。

📈 性能对比

方案复杂度结论
倍增 LCA + 链上取 maxO(N log N + Q(m log N + 深度))✅ 正确且快,官方做法
只输出 LCAO(N log N + Q·m log N)❌ 漏掉"编号最大"这一步
逐点暴力验证所有人O(Q · N · m)⚠️ 答案对但接近 10⁹,易超时
05
算法流程图
建树 + 倍增 LCA + 链上取最大 主流程
开始读入 N 与 f₁ … f_{N−1},用孩子表建树从根 0 开始 BFS:定深度,并填 up[x][0] = 父结点倍增递推 up[x][j] = up[ up[x][j−1] ][j−1]循环:处理第 i 场合作(i = 1 … Q)读入 m 与 m 个员工编号,令 L = 第一个编号对剩下的每个编号 y:L = LCA(L, y)从 L 沿父指针走到根,途中记录编号最大值输出该场合作的主持人编号Q 场合作全部回答完毕下一场合作
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🌳 主持人推演器(LCA + 链上取最大)

第一行输入 N;第二行输入 f₁ … f_{N−1}(N − 1 个数);第三行输入 Q;随后 Q 行每行先给 m,再给 m 个员工编号。程序会逐场展示公共祖先链与选出的主持人。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(倍增 LCA + 链上取最大)

#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;链上取最大"编号最大"不是"最近公共祖先"
⚠️
五个坑:① 求出 LCA 直接输出(漏掉链上取 max,反例会挂);② 假设 fᵢ < i,用倒序循环推深度(遇到 f₁ = 2 这类数据就错);③ 忘记 par[0] = 0,沿链上溯时读到下标 0 以外的垃圾值;④ 用递归 DFS 求深度,N = 10⁵ 的链形树直接爆栈;⑤ LOG 开太小(LOG = 17 时 2¹⁶ = 65536 < 10⁵,深度差抬不上去)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
5
0 0 2 2
3
2 3 4
3 2 3 4
2 1 4
2
2
0
题面样例 1
7
0 1 0 2 1 2
5
2 4 6
2 4 5
3 4 5 6
4 2 4 5 6
2 3 4
2
1
1
1
0
题面样例 2(含一组 hack 数据)
3
0 0
1
2 1 2
0只有老板能同时管住 1 号和 2 号
4
2 0 2
1
2 1 3
2f₁ = 2 比 1 大:必须用孩子表 + BFS 建树
6
2 5 2 2 0
2
2 1 3
2 2 4
5
5
链 2 → 5 → 0:编号最大的是 5,只输出 LCA 会得 2
6
0 1 2 3 4
1
2 4 5
4长链 0→1→2→3→4→5,链上取 max
✅
自查清单:① 是用孩子表 + BFS 建树吗?② par[0] = 0 设了吗?③ 求完 LCA 有没有沿链取 max?④ LOG 够大吗?⑤ 链上走的时候有没有在 0 处停下?

🚨 易错点清单

⚠️
只输出 LCA:题目要的是"能管理所有人的员工中编号最大的",候选人是 LCA 到根的一整条链,必须取链上 max。
⚠️
假设 fᵢ < i:反例 N = 4、f = 2 0 2,倒序推深度会用到尚未计算的 dep[2]。
⚠️
忘记 par[0] = 0:沿父指针上溯到根后没有"停"的条件,会读到越界或死循环。
⚠️
递归求深度:N = 10⁵ 的链会让栈溢出,请用 BFS。
⚠️
倍增层数不够:LOG 至少要满足 2^LOG > N,建议取 18。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(N log N + Q(m log N + N))
空间复杂度
O(N log N)
单次询问
O(m log N + 深度)
最坏总量
约 10⁷ 次操作

时间怎么算的?

空间都用在哪?

倍增表 up[N][18] 用 int 存,约 10⁵ × 18 × 4 B ≈ 7 MB;另有孩子表的边数 O(N)、深度数组与父亲数组各 O(N),整体 O(N log N) 空间很宽裕。

✅ 约 10⁷ 次基础操作,1 秒时限内非常轻松。关键是 Q ≤ 100 这个条件很小,所以"每次询问沿链走一遍"完全承受得起。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// ---------- 倍增 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?为什么?(这正是"链上聚合"思想的另一面:链上什么统计都能顺手做出来。)