LeetCode解題紀錄 2477. Minimum Fuel Cost to Report to the Capital

https://leetcode.com/problems/minimum-fuel-cost-to-report-to-the-capital/

題目

給定一個樹狀結構，總共有 n 個城市與 n-1條路，沒有方向與迴圈，0 是首都，每個城市都有個代表要開車到首都，每前進一個城市都要耗費一公升的油，給定一個參數 seats，代表一台車可以有幾個人可以共乘，要求返回耗費最少的汽油公升數

限制

• 1 ≤ n ≤ 10⁵
• 1 ≤ seats ≤ 10⁵

觀察

• 從 tree 末端城市的代表，一定要獨自開一台車到下個城市
• 每個城市出發的車，是人數除以 seats 的無條件進位值

思路

• 要找到末端城市，可以用 DFS
• 從首都開始找每個通往下個城市的道路，一直找到無法前進時，返回 1 代表要前往首都的代表人數
• 累加遞迴的人數，就是會抵達這個城市的總人數
• 同時累加上個城市過來的人，開車所花費的汽油公升數，注意！這裡並非加總後才統計，每個城市須分開計算

Trial 1

結果

TC：O(n)，SC：O(n)，這個題目的關鍵是在人與油耗數要分別計算統計