[GESP202312六级]工作沟通

题目描述

某公司有 N N N 名员工，编号从 0 0 0 至 N − 1 N-1 N−1。其中，除了 0 0 0 号员工是老板，其余每名员工都有一个直接领导。我们假设编号为 i i i 的员工的直接领导是 f i f_i fi​。

该公司有严格的管理制度，每位员工只能受到本人或直接领导或间接领导的管理。具体来说，规定员工 x x x 可以管理员工 y y y，当且仅当 x = y x=y x=y，或 x = f y x=f_y x=fy​，或 x x x 可以管理 f y f_y fy​。特别地， 0 0 0 号员工老板只能自我管理，无法由其他任何员工管理。

现在，有一些同事要开展合作，他们希望找到一位同事来主持这场合作，这位同事必须能够管理参与合作的所有同事。如果有多名满足这一条件的员工，他们希望找到编号最大的员工。你能帮帮他们吗？

输入格式

第一行一个整数 N N N，表示员工的数量。

第二行 N − 1 N - 1 N−1 个用空格隔开的正整数，依次为 f 1 , f 2 , … f N − 1 f_1,f_2,\dots f_{N−1} f1​,f2​,…fN−1​。

第三行一个整数 Q Q Q，表示共有 Q Q Q 场合作需要安排。

接下来 Q Q Q 行，每行描述一场合作：开头是一个整数 m m m（ 2 ≤ m ≤ N 2 \le m \le N 2≤m≤N），表示参与本次合作的员工数量；接着是 m m m 个整数，依次表示参与本次合作的员工编号（保证编号合法且不重复）。

保证公司结构合法，即不存在任意一名员工，其本人是自己的直接或间接领导。

输出格式

输出 Q Q Q 行，每行一个整数，依次为每场合作的主持人选。

输入输出样例 #1 输入 #1 5 0 0 2 2 3 2 3 4 3 2 3 4 2 1 4 输出 #1 2 2 0 输入输出样例 #2 输入 #2 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 2 1 1 1 0 说明/提示

样例解释 1

对于第一场合作，员工 3 , 4 3,4 3,4 有共同领导 2 2 2 ，可以主持合作。

对于第二场合作，员工 2 2 2 本人即可以管理所有参与者。

对于第三场合作，只有 0 0 0 号老板才能管理所有员工。

数据范围

对于 50 % 50\% 50% 的测试点，保证 N ≤ 50 N \leq 50 N≤50。

对于所有测试点，保证 3 ≤ N ≤ 300 3 \leq N \leq 300 3≤N≤300， Q ≤ 100 Q \leq 100 Q≤100。

提交链接

工作沟通

思路解析 输入与初始化： 输入：首先，程序通过标准输入读取员工数 n n n、每个员工的直接领导 f [ i ] f[i] f[i]（根结点 f [ 0 ] = − 1 f[0] = -1 f[0]=−1），然后读取查询次数 q q q。初始化： f [ i ] f[i] f[i] 存储每个员工的直接领导， f [ 0 ] = − 1 f[0] = -1 f[0]=−1 表示 0 0 0 号员工是老板，没有领导。 n u m [ i ] num[i] num[i] 用于记录员工 i i i 访问的次数，在 DFS 函数中被更新。 DFS递归函数： 递归作用：对于每个员工 x x x，通过递归调用 d f s ( x ) dfs(x) dfs(x) 更新员工 x x x 和其所有上级（即直接领导和间接领导）的访问次数。递归结束条件：当递归到根节点（ f [ x ] = = − 1 f[x] == -1 f[x]==−1）时，结束递归。时间复杂度：对于每个员工 x x x，递归最深可以到达根节点，递归的最大深度为 O ( N ) O(N) O(N)。 查询处理： 每次查询需要找到一位能够管理所有参与合作的员工的主持人。处理过程： m m m：表示参与合作的员工数量。先使用 memset(num, 0, sizeof(num)) 清空访问次数数组 n u m num num。对每个员工 x x x 执行 d f s ( x ) dfs(x) dfs(x)，更新员工及其领导的访问次数。然后遍历所有员工（从编号大的员工开始）来检查是否能够管理所有参与合作的员工（即查看 n u m [ i ] = = m num[i] == m num[i]==m）。找到符合条件的员工后，输出该员工的编号，停止遍历。 时间复杂度分析： 每个查询： d f s ( x ) dfs(x) dfs(x) 会对每个参与合作的员工进行递归，最坏情况下，递归的时间复杂度是 O ( N ) O(N) O(N)。如果有 m m m 个员工参与合作，时间复杂度为 O ( m ∗ N ) O(m * N) O(m∗N)。遍历 n n n 个员工来查找符合条件的主持人，时间复杂度为 O ( N ) O(N) O(N)。所以每个查询的时间复杂度是： O ( m ∗ N + N ) O(m * N + N) O(m∗N+N)，简化为 O ( m ∗ N ) O(m * N) O(m∗N)，因为 m ≤ N m ≤ N m≤N。 总体时间复杂度： q q q 个查询，总时间复杂度为 O ( q ∗ m ∗ N ) O(q * m * N) O(q∗m∗N)。如果 m m m 接近 N N N，最终时间复杂度为 O ( q ∗ N 2 ) O(q * N^2) O(q∗N2)。

参考代码：

#include <bits/stdc++.h> using namespace std; const int MAX_N = 3e2 + 9; int n, q, f[MAX_N], m, x, num[MAX_N]; void dfs(int x) { num[x]++; // num[i]：记录编号i访问的次数 if (f[x] == -1) return; dfs(f[x]); } int main() { cin >> n; f[0] = -1; //根结点的直接领导 for (int i = 1; i <= n - 1; i++) cin >> f[i]; // 编号为i的员工的直接领导为f[i] cin >> q; while (q--) // q场合作需要安排 { cin >> m; // 合作的员工的数量 memset(num , 0 , sizeof(num)); for (int i = 1; i <= m; i++) { cin >> x; // 参与合作的员工编号 dfs(x); } for(int i = n - 1; i >= 0; i--) //编号从大到小 { if(num[i] == m) //编号为i访问了m次 说明i能够管理者m个合作的员工 { cout << i << endl; break; } } } return 0; }