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;
}
};