GESP 题解库 / 6 级题解 / [GESP202312 六级] 工作沟通 · 第 19 / 27 题
GESP202312 六级 · P10109 · 简单

工作沟通

每场合作找一个能管理所有人的主持者,若有多个则取编号最大的。

📊
N ≤ 300, Q ≤ 100
数据规模
🔢
int
编号范围
⚡
O(N² + Q·m·N)
时间复杂度
🎯
祖先集合求交
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

公司有 N 名员工(编号 0 ~ N−1),0 号是老板,其余每人有直接领导 fᵢ。规定 x 能管理 y 当且仅当 x = y,或 x = f_y,或 x 能管理 f_y(即x 是 y 的祖先或本人)。

每场合作给出若干参与者,要找一位能管理所有参与者的主持者;若有多人满足,选编号最大的那位。

💡
人话翻译:条件"能管理所有人"等价于"这位主持者是所有参与者的公共祖先(或本人)"。
所以解题分两步:① 预处理每个员工的完整祖先链(含本人,一直到 0 号);② 对每场合作,把所有人的祖先集合求交集,再取其中编号最大的。
N ≤ 300、Q ≤ 100 很小,直接暴力求交完全够快。

🔍 关键词提取

祖先链集合求交树上关系暴力枚举

已知条件

项目说明
输入第一行 N;第二行 f₁…f_{N−1};第三行 Q;随后 Q 行每行 m 与参与者
输出每行一个主持人编号
数据范围3 ≤ N ≤ 300,Q ≤ 100
管理关系x 管理 y ⟺ x 在 y 的祖先链上(含 y 自身)
选择规则所有可行者中取编号最大

需要解决的问题

02
思维导图
整理解题思路的全貌
👔 祖先集合求交
🌳 建关系
员工 y 的领导是 f_y
0 号是老板(根)
每个员工可向上走任意层
一直到根 0
📋 预处理
对每个 y 收集祖先链(含自己)
用布尔数组标记"谁能管 y"
N ≤ 300 → 总规模很小
也可以直接用 vector 存
🔍 每场合作
取第一个人的名单作为候选
依次与其他人的名单求交
交集中取最大编号
输出该编号
⚠️ 易错点
把"编号最大"当成"层级最深"
忘记"本人也能管理自己"
交集的初始集合没设对
认为 f_i 一定小于 i
03
样例手算推导
两个样例的完整推演

🧮 样例 1:N = 5,f = [0, 0, 2, 2]

f₁ = 0、f₂ = 0、f₃ = 2、f₄ = 2。所以:2、3、4 号都直接向 0 号汇报?不——f₃ = 2 表示 3 号的领导是 2 号。

员工直接领导完整祖先链(含自己)
0(老板)0
101, 0
202, 0
323, 2, 0
424, 2, 0
1
第 1 场:参与者 3、4

3 的名单:{3, 2, 0}

4 的名单:{4, 2, 0}

交集:{2, 0}

取编号最大 → 2

输出 2 ✓

2
第 2 场:参与者 2、3、4

2 的名单:{2, 0}

与 {3, 2, 0} 求交 → {2, 0}

再与 {4, 2, 0} 求交 → {2, 0}

取最大 → 2

输出 2 ✓

3
第 3 场:参与者 1、4

1 的名单:{1, 0}

4 的名单:{4, 2, 0}

交集:{0}(只有老板)

取最大 → 0

输出 0 ✓

输出 2、2、0 ✓ 与样例一致

🔑
注意第 3 场的解释:题目说"只有 0 号老板才能管理所有员工"——因为 1 号和 4 号分属不同分支(1 的上级是 0,4 的上级是 2、再往上才是 0),除了老板 0 号,没有别人能同时管住这两个人。

🧮 样例 2:验证"取最大编号"而非"层级最深"

N = 7,f = [0, 1, 0, 2, 1, 2]:

员工直接领导完整祖先链
0—0
101, 0
212, 1, 0
303, 0
424, 2, 1, 0
515, 1, 0
626, 2, 1, 0
1
第 1 场:4、6

4 的名单:{4, 2, 1, 0}

6 的名单:{6, 2, 1, 0}

交集:{2, 1, 0}

取最大编号 → 2(也是层级最深)

输出 2 ✓

2
第 3 场:4、5、6

4:{4, 2, 1, 0}

5:{5, 1, 0}

6:{6, 2, 1, 0}

三者交集:{1, 0}

取最大编号 → 1

输出 1 ✓

3
第 5 场:3、4

3:{3, 0}

4:{4, 2, 1, 0}

交集:{0}

→ 0

输出 0 ✓

输出 2、1、1、1、0 ✓ 与样例一致

⚠️
关于"取最大编号"这一点:本题的样例里,编号最大的恰好也是层级最深的(即 LCA),但题目要求的是"编号最大",不是"层级最深"。
如果树的结构允许"浅层结点的编号比深层结点更大",两者就会不同。所以我们直接求"祖先集合的交集再取最大值",而不是求 LCA——这样最稳妥。
04
解法对比
祖先集合求交 vs 逐对求 LCA

⚔️ 解法对比

🟢 祖先集合求交(推荐) 推荐

预处理每人祖先链,每场合作求交集取最大值

  • 预处理 O(N²)
  • 每场合作 O(m · N)
  • 总计 ≤ 100 × 300 × 300 = 9 × 10⁶
  • 代码 30 行
💡
为什么这样最稳:题目要的是"编号最大的可行者",而不是"层级最深的祖先"。直接枚举"所有公共祖先"再取最大值,完全贴合题意,不会因为树的结构特殊而错。

🟠 逐对求 LCA

先求所有参与者的 LCA,但还要再考虑 LCA 的祖先们

  • 求 LCA 本身是对的
  • 但"最大编号"可能出现在 LCA 的祖先上
  • 容易漏掉
  • 还需要额外遍历祖先
⚠️
关键区别:如果题目问"最深的主持者",那就是 LCA;但本题问"编号最大的",必须把 LCA 及它的所有祖先都纳入比较。
所以"求交集取最大"反而更直接。

📈 性能对比

方案做法风险
祖先集合求交交集后取 max低
求 LCA还需再比较其祖先中(易漏)
05
算法流程图
预处理祖先链后逐场求交
开始读入 N 和 f₁…f_{N−1}对每个员工 y 从 0 到 N−1沿领导链向上走,把 y 及其所有祖先标记进名单 anc[y]读入 Q;对每场合作先取第一位参与者的名单作为候选集依次处理其余参与者候选集与当前参与者的名单求交集取交集中编号最大的员工并输出结束处理下一位参与者
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

👔 主持人查找器

第一行输入 N,第二行输入各员工的领导,第三行输入 Q,随后 Q 行输入参与者。

结果会显示在这里

点按钮开始 →

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

💻 完整 C++ 代码

#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;
}
🔑
为什么用"祖先集合求交"而不是"求 LCA"?因为题目要求"编号最大",而不是"层级最深"。
集合交集恰好就是"所有可行主持人"的完整名单,从大到小扫一遍取第一个,既简洁又绝对不会漏。
另外注意 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 成立(题目只保证无环,不一定编号递增);④ 输出顺序与输入顺序不一致。
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
3
0 0
1
2 1 2
0两人分属不同分支,只能找老板
3
0 1
1
2 1 2
12 的上级是 1,1 能同时管住 1 和 2
3
0 0
1
2 0 1
0老板只能自我管理,无法被别人管理
✅
自查清单:① 链含自己吗?② 交集初始化对吗?③ 取的是最大编号吗?

🚨 易错点清单

⚠️
漏掉本人:祖先链必须包含自己,否则"参与者自己当主持人"的情况会漏。
⚠️
候选集初始化错:应从第一位参与者的祖先集合开始求交。
⚠️
误以为编号递增:题目只保证无环,所以要用"取最大编号"而不是"找最深结点"。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

预处理
O(N²)
每场合作
O(m · N)
N 最大
300
总运算量
≤ 9 × 10⁶

时间怎么算的?

空间都用在哪?

一个 N × N 的布尔表(300 × 300),非常小。

✅ 约 900 万次布尔运算,瞬间完成。本题数据范围小,暴力求交是最省心的解法。

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

🔗 常用技巧小抄

// 树上"谁能管理谁"的通用处理
// 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 较小时的通用做法
🌟
思考题:如果 N 放大到 10⁵、Q 也到 10⁵,本题该怎么做?(提示:就不能用 O(N²) 的布尔表了——需要先求所有参与者的 LCA(用倍增法 O(N log N) 预处理 + O(m log N) 查询),再在"LCA 及其祖先"中找编号最大的。而"编号最大"这个要求仍然需要额外处理——这也说明读清题目的"选择规则"有多重要。)