工作沟通 题解

一、题目分析

本题描述了一家公司内部的管理关系：公司共有 $N$ 名员工，编号 $0$ 到 $N-1$。其中 $0$ 号是老板，其余每名员工 $i$ 都有一位直接领导 $f_i$。管理关系满足：

• 员工 $x$ 可以管理员工 $y$，当且仅当 $x = y$，或 $x = f_y$，或 $x$ 可以管理 $f_y$。

换句话说，$x$ 能管理 $y$，等价于在以 $0$ 为根的树中，$x$ 是 $y$ 的祖先（或 $x=y$）。公司结构保证不存在环，即这是一棵有根树。

现在有 $Q$ 场合作，每场合作给出若干参与员工，需要选出一名主持人，他必须能管理所有参与员工，即他是所有参与员工的公共祖先。若有多个满足条件的员工，选择编号最大的那一个。

二、解题思路

2.1 简化问题

题目本质上是要在一棵树上，多次给定一个点集，求出该点集的公共祖先中编号最大者。

公共祖先中深度最深的那个其实就是最近公共祖先（LCA），但深度最深不一定是编号最大。例如，编号较大的节点可能在更浅的位置。由于 $N \le 300$，数据规模很小，我们可以采用较为直接的方法。

2.2 暴力枚举

对于每个询问，我们已知参与员工集合 $S$。一个员工 $x$ 能成为主持人，必须满足：

1. $x$ 是 $S$ 中所有节点的祖先（或等于其中之一）；
2. 在满足条件的 $x$ 中，编号最大。

一个简单的暴力思路是：从编号 $N-1$ 到 $0$ 依次判断每个节点，找到的第一个可行节点就是答案。

为了判断节点 $x$ 是否能管理集合 $S$ 中的所有员工，我们可以从 $x$ 出发做一次 DFS 或 BFS，标记所有能被 $x$ 管理的节点（即 $x$ 的子树）。然后检查 $S$ 中的所有节点是否都被标记。如果都被标记，说明 $x$ 满足条件。

为了优化一点枚举顺序，我们注意到：任何公共祖先的深度不可能超过 $S$ 中节点的最小深度。因此，我们可以先算出 $S$ 中所有节点的深度，记最小深度为 min_dep。枚举时只考虑深度小于等于 min_dep 的节点即可。

2.3 算法步骤

1. 建树
   读入 $N$ 和 $f_1 \dots f_{N-1}$，将 $f_i$ 作为 $i$ 的父亲，同时记录每个节点的孩子列表（方便 DFS）。

2. 计算深度
   利用递归或递推计算每个节点的深度（$0$ 号深度为 $0$）。

3. 处理询问
   对于每个询问：

   • 读入参与人数 $m$ 以及 $m$ 个员工编号，存入数组 vec。
   • 计算 min_dep = min(dep[vec[i]])。
   • 从 $i = N-1$ 向下枚举到 $0$：
     • 如果 dep[i] > min_dep，跳过（不可能是公共祖先）。
     • 否则，执行一次 DFS 从 $i$ 出发，标记所有能被 $i$ 管理的节点。
     • 检查 vec 中的每个节点是否都被标记。
     • 如果全部标记，输出 $i$ 并结束本次询问。

三、算法实现

3.1 深度计算

cpp
复制
1int getdep(int x) {
2    if (x == 0) return 0;
3    return getdep(fa[x]) + 1;
4}

由于 $N$ 很小，直接用递归不会爆栈。

3.2 判断能否管理

cpp
复制
1bool check(int x, int n, const vector<int>& vec) {
2    memset(vis, 0, sizeof(vis)); // 重置标记数组
3    dfs(x);                      // 从 x 出发 DFS 标记子树
4    for (int y : vec)
5        if (!vis[y]) return false;
6    return true;
7}

DFS 函数：

cpp
复制
1void dfs(int x) {
2    vis[x] = true;
3    for (int y : ch[x])
4        dfs(y);
5}

3.3 主流程

cpp
复制
1for (int i = n - 1; i >= 0; i--) {
2    if (dep[i] <= mnd && check(i, n, vec)) {
3        printf("%d\n", i);
4        break;
5    }
6}

由于从大到小枚举，第一个满足条件的必定是编号最大的公共祖先。

四、时间复杂度分析

• 预处理：计算深度 $O(N)$。
• 每个询问：
  • 计算最小深度：$O(m)$。
  • 枚举候选节点：$O(N)$ 次。
  • 每次 check 需要 DFS 标记子树：$O(N)$，并检查 $m$ 个点：$O(m)$。
  • 单次询问总复杂度：$O(N(N + m))$。
• 总体复杂度：$O(Q \cdot N(N + m))$。

代入最大值 $N=300, Q=100, m \le 300$，最大操作次数约为 $100 \times 300 \times 600 = 1.8 \times 10^7$，在 1s 时限内可以通过。

五、参考代码及解释

cpp
复制
1#include <cstdio>
2#include <cstdlib>
3#include <cstring>
4#include <algorithm>
5#include <string>
6#include <map>
7#include <cmath>
8#include <vector>
9using namespace std;
10
11const int N = 305;
12int fa[N], dep[N];
13bool vis[N];
14vector<int> ch[N];
15
16// 递归计算深度
17int getdep(int x) {
18    return x == 0 ? 0 : getdep(fa[x]) + 1;
19}
20
21// 从 x 开始深度优先搜索，标记所有可管理的员工
22void dfs(int x) {
23    vis[x] = 1;
24    for (int y : ch[x])
25        dfs(y);
26}
27
28// 检查 x 是否能管理 vec 中的所有员工
29bool check(int x, int n, const vector<int>& vec) {
30    for (int i = 0; i <= n; i++)
31        vis[i] = 0;
32    dfs(x);
33    for (int y : vec)
34        if (!vis[y])
35            return 0;
36    return 1;
37}
38
39int main() {
40    int n;
41    scanf("%d", &n);
42    // 读入父节点，建立子节点列表
43    for (int i = 1; i < n; i++) {
44        scanf("%d", &fa[i]);
45        ch[fa[i]].push_back(i);
46    }
47    
48    // 计算每个节点的深度
49    for (int i = 1; i < n; i++)
50        dep[i] = getdep(i);
51
52    int q;
53    scanf("%d", &q);
54    while (q--) {
55        int m, mnd = n + 1;
56        scanf("%d", &m);
57        vector<int> vec(m);
58        for (int i = 0; i < m; i++) {
59            scanf("%d", &vec[i]);
60            mnd = min(mnd, dep[vec[i]]);   // 参与员工的最小深度
61        }
62
63        // 从编号大到小枚举，找到第一个公共祖先
64        for (int i = n - 1; i >= 0; i--)
65            if (dep[i] <= mnd && check(i, n, vec)) {
66                printf("%d\n", i);
67                break;
68            }
69    }
70
71    return 0;
72}

代码解释：

• fa 数组存每个节点的父节点，ch 是每个节点的孩子列表。
• getdep(x) 递归求深度，因为 $N$ 很小，所以用递归也很安全。
• check(x, n, vec) 用 DFS 标记 $x$ 的子树，并逐一验证参与者是否被标记。
• 主循环中 mnd 用来剪枝，减少不必要的枚举。
• 枚举时从 $n-1$ 往下找，第一个成功的即为编号最大的公共祖先。

本题利用了数据规模较小的特点，采用暴力枚举加 DFS 标记的方法，代码简单，思路清晰，适合在考场上快速实现。