LeetCode 1376. 通知所有员工所需的时间
目录
题目描述
题意分析
公司有
n名员工，编号0到n-1。manager[i]是员工i的直属上级，总负责人headID的上级是-1。informTime[i]表示员工i把消息通知给他所有直属下属所需的分钟数——注意是「所有下属一起」而不是「每个下属各花这么久」，所以同一层的下属是并行收到消息的。问从headID开始，让全体员工都收到消息需要多少分钟。「并行」这两个字是本题的核心语义。一个上级花
informTime[i]分钟之后，他的所有直属下属同时收到消息，然后各自独立地继续往下传。所以总耗时不是把所有informTime加起来，而是取所有传播链路中最慢的那一条。输入格式给的是「每个人的父亲」，这是一棵用父指针数组表示的树，
headID是根，叶子（没有下属的员工）的informTime保证为 0。题目保证这个结构是合法的树，不会出现环或多根。由此看清问题的本质：求根到所有叶子的路径中，边权之和最大的那一条，其中从员工
i到他任一下属的边权是informTime[i]。这是一道带权树上的最长路问题，而不是最短路。约束里
n最大 $10^5$，informTime[i]最大 1000。最坏情况下树退化成一条链，路径权和可达 $10^5 \times 1000 = 10^8$，仍在int范围内，不必担心溢出；但链式退化意味着递归深度可能到 $10^5$，栈空间需要留意。边界要留意四点：
n = 1时只有负责人自己，答案是 0；叶子的informTime是 0，不贡献时间；输入给的是父指针，要用它反向建出子指针才能自顶向下传播；答案是路径最大值，不是所有informTime的总和。
解法：树形 DFS/BFS
核心思路
先想一个朴素做法：对每个员工，顺着
manager一路往上追到headID，把沿途所有上级的informTime加起来，就是这名员工收到消息的时刻；最后取所有员工的最大值。这是正确的，但每次追溯的代价是该员工的深度，链式树上总代价 $O(n^2)$，$10^5$ 规模下是 $10^{10}$ 次操作，必然超时。瓶颈很清楚：不同员工的追溯路径高度重叠，靠近根的那一段被反复累加。反过来自顶向下走一遍，每条边只经过一次，就能把所有重复消去。
但输入只给了父指针，从上往下走不了。所以第一步必须反向建图：开一个长度为
n的邻接表，遍历每个i，把i追加到g[manager[i]]里（manager[i] == -1的根跳过）。这一步把「谁是我的上级」翻译成「我有哪些下属」，是自顶向下传播的前提。建好子节点表后，用 BFS 自顶向下传播。状态
(u, time)表示员工u在time分钟时收到消息。若v是u的直属下属，那么u收到消息后还需informTime[u]分钟完成通知，所以转移是receive[v] = time + informTime[u]。这里最容易错的是路径费用归属：
informTime[u]是从u走向任一下属的边权，不是u收到消息之前的费用。因此员工u的收到时刻，等于从headID到u的路径上所有祖先的informTime之和，不包含informTime[u]自己；叶子的informTime也不会计入答案。正确性说明：BFS 的不变量是：员工出队时携带的
time，恰好等于负责人到该员工唯一管理链上的边权和。根的空路径和为 0；若该结论对u成立，则给孩子加上边u → v的权informTime[u]后，对v也成立。按树的层次归纳，所有员工的收到时刻都计算正确。所有分支并行传播，所以全员收到消息的时刻是这些
time的最大值，而不是总和。题目保证管理关系是一棵树，每个员工只会入队一次；选择 BFS 还能避开最坏 $10^5$ 层递归带来的栈风险。
解题步骤
- 先反向建邻接表
g，g[m]存所有以m为上级的员工。 输入是父指针，而传播是自上而下的，不建反向表就无法从根出发遍历。建表时要跳过manager[i] == -1的根，否则会访问g[-1]导致越界。- 邻接表要为每名员工放入一个空列表。 Java 的
new ArrayList<>(n)只设置容量，列表长度仍是 0，必须循环add(new ArrayList<>())；Go 的make([][]int, n)已创建n个可直接追加的切片槽位。- 把
(headID, 0)入队。 负责人在 0 分钟时已经知道消息；根不一定是 0 号员工，起点必须使用参数headID。- 弹出
(u, time)时更新全局最大值。time是u的收到时刻，所有员工并行传播，最终答案就是所有收到时刻的最大值。- 给每个直属下属
v入队(v, time + informTime[u])。 加的是上级u的通知时间，因为这段耗时发生在边u → v上；不能加informTime[v]。- 不需要
visited数组。 输入保证是一棵树，每个节点只有一个父亲，从根出发不会重复访问任何节点，也不存在环。多写的访问标记是冗余代码。- 队列清空后返回最大收到时刻。
n = 1时队列只处理(headID, 0)，自然返回 0。以
n = 7、headID = 6、manager = [1, 2, 3, 4, 5, 6, -1]、informTime = [0, 6, 5, 4, 3, 2, 1]走一遍（正确答案是 21）。先反向建表：
i = 0的上级是 1，g[1] = [0]；i = 1的上级是 2，g[2] = [1]；i = 2的上级是 3，g[3] = [2]；i = 3的上级是 4，g[4] = [3]；i = 4的上级是 5，g[5] = [4]；i = 5的上级是 6，g[6] = [5]；i = 6的上级是-1，跳过。这棵树是一条链6 → 5 → 4 → 3 → 2 → 1 → 0。从
(6, 0)开始，链上收到时刻依次为：员工 5 在0 + informTime[6] = 1分钟收到；员工 4 在1 + informTime[5] = 3分钟收到；之后员工 3、2、1、0 的收到时刻依次是 6、10、15、21。最大值为 21。注意员工 0 自己的informTime[0]不参与，因为消息到达员工 0 时任务已经完成。再看并行用例：
headID = 2且五名员工都是 2 的直属下属，informTime[2] = 1。五个状态都会以时刻 1 入队，答案仍是 1，而不是1 * 5 = 5；一次通知同时覆盖所有直属下属。
代码实现
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
class Solution {
public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) {
// 输入是父指针，反向建出子指针才能自顶向下传播。
List<List<Integer>> g = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
g.add(new ArrayList<>());
}
for (int i = 0; i < n; i++) {
int m = manager[i];
if (m != -1) {
g.get(m).add(i);
}
}
Queue<int[]> queue = new ArrayDeque<>();
queue.offer(new int[] {headID, 0});
int answer = 0;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
int employee = cur[0];
int receiveTime = cur[1];
answer = Math.max(answer, receiveTime);
for (int subordinate : g.get(employee)) {
queue.offer(new int[] {
subordinate, receiveTime + informTime[employee]
});
}
}
return answer;
}
}
func numOfMinutes(n int, headID int, manager []int, informTime []int) int {
g := make([][]int, n)
for i := range manager {
if manager[i] != -1 {
g[manager[i]] = append(g[manager[i]], i)
}
}
type state struct {
employee, receiveTime int
}
queue := []state{{headID, 0}}
answer := 0
for head := 0; head < len(queue); head++ {
cur := queue[head]
if cur.receiveTime > answer {
answer = cur.receiveTime
}
for _, subordinate := range g[cur.employee] {
queue = append(queue, state{
subordinate,
cur.receiveTime + informTime[cur.employee],
})
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(n)$。反向建图扫描一次
manager，BFS 中每名员工入队、出队一次，每条管理边遍历一次。- 空间复杂度：$O(n)$。邻接表保存
n - 1条边，队列最多保存n个状态；使用迭代 BFS，不消耗与树高相关的递归栈。
关键点总结
- 「并行」对应取最大值，「串行」对应求和：一个上级同时通知所有下属，所以子树耗时由最慢的分支决定。读题时把这类词精确翻译成聚合方式，是这道题唯一的建模难点。
- 父指针输入要先反向建表：给定
manager[i]是自下而上的表示，而传播是自上而下的，两者方向相反。见到「每个点只有一个父亲」的数组输入，第一反应就该是建反向邻接表。- 状态定义为员工的收到时刻：
receive[child] = receive[parent] + informTime[parent]。它等于根到该员工路径上的边权和，费用属于父节点发出的边。- 树结构下不需要
visited：每个节点唯一父亲、从根出发不会成环。判断能否省掉访问标记的依据是输入是否保证无环，而不是凭感觉。- 叶子的
informTime不计入答案：员工一旦收到消息就完成了对该员工的通知；只有他继续通知下属时，自己的耗时才成为下一条边的权。- 面试视角：先说「并行取最大路径和」，再把父指针反向成孩子表，定义收到时刻并写出转移。选 BFS 是因为
n可达 $10^5$，比递归 DFS 更稳妥。
易错点总结
- 错误写法：把各分支耗时求和 → 负责人有五名直属下属且
informTime[headID] = 1时，五人会同时在 1 分钟收到消息；累加会误算成 5。- 错误写法：对每名员工都沿
manager追到根且不记忆化 → 退化链上会反复经过同一前缀，总时间达到 $O(n^2)$。- 错误写法：从员工 0 开始递归而不是从
headID→ 用例n = 7、headID = 6中员工 0 是叶子，dfs(0)直接返回 0，正确答案是 21。- 错误写法：建表时不跳过
manager[i] == -1→ 用例中根的manager是-1，执行g[-1].add(i)直接数组越界异常。- 错误写法：以为
new ArrayList<>(n)已经创建了n个元素 → 它只预留容量，直接调用g.get(manager[i])会下标越界；还要显式加入n个空列表。- 错误写法：孩子时刻加
informTime[child]→ 在链0 → 1中，员工 1 的收到时刻应为informTime[0]；加孩子的值会漏掉负责人真正花费的通知时间。- 错误写法：用 BFS 但队列里只存员工编号不存时刻，靠层数推算时间 → 用例中不同分支的
informTime不同，同一层的员工收到消息的时刻并不相同，按层计时会得到与真实时刻无关的结果。- 过度实现：把管理边建成双向，再增加
visited防止回头 → 输入本就给出父子方向，传播只会从上级到下属；双向边和访问数组不能增加正确性，只会让状态与代码更复杂。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 104. 二叉树的最大深度 | 简单 | 同为「子树取最大值再加一」的后序合成，边权固定为 1 |
| 543. 二叉树的直径 | 简单 | 路径可在节点处向两侧拐弯，需要返回值与全局答案分离 |
| 124. 二叉树中的最大路径和 | 困难 | 带权最长路且权可为负，向上返回时要对负贡献取 0 |
| 1245. 树的直径 | 中等 | 一般树上的最长路，可用两次 BFS 或一次树形 DP |
| 310. 最小高度树 | 中等 | 求让树高最小的根，靠逐层剥叶子找中心，与本题固定根形成对照 |
| 1466. 重新规划路线 | 中等 | 同样需要处理边的方向，但要同时建正反两向边并在遍历时区分原方向 |
| 1361. 验证二叉树 | 中等 | 输入也是数组形式的父子关系，重点是验证结构合法性而非在其上计算 |
| 743. 网络延迟时间 | 中等 | 图上带权传播且存在多条路径，必须用 Dijkstra 取最小而非树上直接递推 |
| 207. 课程表 | 中等 | 有向图判环，同样需要由「前置关系」反向建邻接表 |
| 210. 课程表 II | 中等 | 在拓扑序基础上输出顺序，可对比本题不需要拓扑排序的原因是输入已是树 |
| 199. 二叉树的右视图 | 中等 | 层序遍历的典型应用，适合练习本题 BFS 改写时的队列组织 |
| 129. 求根节点到叶节点数字之和 | 中等 | 信息自顶向下传参累积，与本题自底向上返回构成两种递归方向的对照 |
| 979. 在二叉树中分配硬币 | 中等 | 后序上传「盈亏差」并在全局累加，训练返回值语义的设计 |
| 1120. 子树的最大平均值 | 中等 | 返回值需打包多个分量，答案在每个节点更新而非只看根 |