MediumRating 2012
2477. Minimum Fuel Cost to Report to the Capital
treedepth-first-searchbreadth-first-searchgraph
解題說明
Minimum Fuel Cost to Report to the Capital
題目描述：
給定一棵 n 個節點的樹，根節點為 0（首都）。每個非根節點恰有一位代表。每個城市有一輛車，最多坐 seats 人。每條邊消耗 1 單位燃料。所有代表需要抵達首都。求最少的總燃料消耗。
解題思路： 使用 DFS 自底向上計算：
- 對於每個子樹，計算需要通過子樹根到父節點的邊的人數
people。 - 通過該邊所需的車輛數 =
ceil(people / seats)。 - 燃料消耗 = 車輛數（因為每輛車過一條邊消耗 1 單位燃料）。
- 從葉節點開始，人數逐層累加上去。
C++ 解法
複雜度分析
時間複雜度：O(n) — DFS 遍歷每個節點一次。
空間複雜度：O(n) — 鄰接表和遞迴堆疊深度。
虛擬碼
1. Build adjacency list from roads
2. Define dfs(node, parent) -> number of people in subtree:
a. people = 1 (current node's representative)
b. For each child of node (not parent):
- people += dfs(child, node)
c. If node != 0 (not root):
- totalFuel += ceil(people / seats)
d. Return people
3. Call dfs(0, -1)
4. Return totalFuel其他解法
BFS 拓撲排序 O(n)：從葉節點開始 BFS，逐層向根聚合人數和燃料。用入度陣列驅動拓撲排序。避免遞迴深度問題但程式碼略長。
迭代 DFS O(n)：用顯式堆疊模擬 DFS，適合避免遞迴堆疊溢出的場景。
延伸思考
- 如果每條邊的油耗不同（帶權邊），做法如何修改？
- 如果代表可以在中途換車（在任何城市下車後搭另一輛車），結果會更優嗎？
- 如果根節點不是 0 而是可以自由選擇，如何找到使總油耗最小的首都位置？