[GESP202312 六级] 工作沟通

题目描述

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

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

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

输入格式

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

第二行 $N-1$ 个用空格隔开的正整数，依次为 $f_1,f_2,\dots f_{N-1}$。

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

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

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

输出格式

输出 $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$ 有共同领导 $2$ ，可以主持合作。

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

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

数据范围

对于 $50\%$ 的测试点，保证 $N\le 50$。

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

提交链接

工作沟通

思路解析

1. 输入与初始化：

• 输入：首先，程序通过标准输入读取员工数 $n$、每个员工的直接领导 $f[i]$（根结点 $f[0]=-1$），然后读取查询次数 $q$。
• 初始化：$f[i]$ 存储每个员工的直接领导，$f[0]=-1$ 表示 $0$ 号员工是老板，没有领导。
• $num[i]$ 用于记录员工 $i$ 访问的次数，在 DFS 函数中被更新。

2. DFS递归函数：

• 递归作用：对于每个员工 $x$，通过递归调用 $dfs(x)$ 更新员工 $x$ 和其所有上级（即直接领导和间接领导）的访问次数。
• 递归结束条件：当递归到根节点（$f[x]==-1$）时，结束递归。
• 时间复杂度：对于每个员工 $x$，递归最深可以到达根节点，递归的最大深度为 $O(N)$。

3. 查询处理：

• 每次查询需要找到一位能够管理所有参与合作的员工的主持人。
• 处理过程：
  • $m$：表示参与合作的员工数量。
  • 先使用 memset(num, 0, sizeof(num)) 清空访问次数数组 $num$。
  • 对每个员工 $x$ 执行 $dfs(x)$，更新员工及其领导的访问次数。
  • 然后遍历所有员工（从编号大的员工开始）来检查是否能够管理所有参与合作的员工（即查看 $num[i]==m$）。
  • 找到符合条件的员工后，输出该员工的编号，停止遍历。

4. 时间复杂度分析：

• 每个查询：
  • $dfs(x)$ 会对每个参与合作的员工进行递归，最坏情况下，递归的时间复杂度是 $O(N)$。如果有 $m$ 个员工参与合作，时间复杂度为 $O(m\ast N)$。
  • 遍历 $n$ 个员工来查找符合条件的主持人，时间复杂度为 $O(N)$。
  • 所以每个查询的时间复杂度是：$O(m\ast N+N)$，简化为 $O(m\ast N)$，因为 $m\le N$。
• 总体时间复杂度：
  • $q$ 个查询，总时间复杂度为 $O(q\ast m\ast N)$。如果 $m$ 接近 $N$，最终时间复杂度为 $O(q\ast N^2)$。

参考代码：

#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;
}