2477. Minimum Fuel Cost to Report to the Capital
給一棵 tree，有 n 個點代表 n 個城市，
每座城市都有車可以通往其他相鄰的城市，一台車最多可以一次載 seats 個人，
現在每座城市都有一個人要到 0 號城市，求最少需要幾台車。
Example 1:
Input: roads = [[0, 1], [0, 2], [0, 3]], seats = 5
Output: 3
Explanation:
https://i.imgur.com/tIgPJaJ.png
1、2、3 號城市各需要 1 台車通往 0 號城市。
Example 2:
Input: roads = [[3, 1], [3, 2], [1, 0], [0, 4], [0, 5], [4, 6]], seats = 2
Output: 7
Explanation:
https://i.imgur.com/1VnMzZn.png
把每條邊的值加一加就能得到 7
Example 3:
Input: roads = [], seats = 1
Output: 0
Explanation:
只有 0 號點存在，不需要任何車
解題思路：
從 0 號點開始進行 DFS，數每條連出去的邊各自有多少 children，
把 children 的個數除以 seats 後取上高斯就是這條邊至少需要多少車，
然後每條邊加一加就是全部需要多少台車。
C++ code:
class Solution {
public:
long long dfs(const vector<vector<int>> &edge, int id, int parent, long
long &ans, int seats){
int sum = 0;
for(auto to : edge[id]){
if(to == parent) continue;
long long res = dfs(edge, to, id, ans, seats);
sum += res;
ans += ceil((double)res / seats);
}
return sum + 1;
}
long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
vector<vector<int>> edge(roads.size() + 1);
for(auto e : roads){
edge[e[0]].push_back(e[1]);
edge[e[1]].push_back(e[0]);
}
long long ans = 0;
dfs(edge, 0, -1, ans, seats);
return ans;
}
};

大師 你好早