MediumRating 1561
1376. Time Needed to Inform All Employees
treedepth-first-searchbreadth-first-search
解題說明
Time Needed to Inform All Employees
題目描述：
一家公司有 n 個員工，從 0 到 n-1 編號。headID 是總經理。manager[i] 是第 i 個員工的直屬上司，informTime[i] 是第 i 個員工通知所有直屬下屬所需的時間。總經理的 manager[headID] = -1。求總經理通知所有員工所需的總時間。
解題思路：
這本質上是一棵以 headID 為根的樹。我們需要找出從根到所有葉節點的最長路徑（路徑上的 informTime 之和）。使用 DFS 遍歷：先建立鄰接表（上司 → 下屬列表），然後從根節點開始 DFS，對每個節點，遞迴計算通知其所有子樹的最大時間，加上該節點自身的 informTime。答案就是根節點的 DFS 結果。
C++ 解法
複雜度分析
時間複雜度：O(n) — 每個節點恰好訪問一次。
空間複雜度：O(n) — 鄰接表 O(n) 加上遞迴堆疊深度最壞 O(n)。
虛擬碼
1. Build adjacency list: for each employee i, add i to children[manager[i]]
2. DFS(node):
a. maxTime = 0
b. For each child in children[node]:
- maxTime = max(maxTime, DFS(child))
c. Return informTime[node] + maxTime
3. Return DFS(headID)其他解法
BFS 層序遍歷：從根節點開始 BFS，佇列存放 (節點, 累計時間) 對。每層將 informTime 加到累計時間上。追蹤全局最大累計時間。時間 O(n)，空間 O(n)。
自底向上 DFS（無需建樹）：從每個葉節點往上走到根，累加路徑上的 informTime。搭配記憶化避免重複計算。時間 O(n)，但常數較大且不如建樹直觀。
延伸思考
- 若每個員工通知不同下屬的時間不同（而非同時通知所有下屬），如何修改？
- 若要找出最後被通知到的員工是誰（而非只求時間），如何修改？
- 若公司結構不是樹而是有向無環圖（DAG），如何求解？