给你一棵 n 个节点的树(一个无向、连通、无环图),每个节点表示一个城市,编号从 0 到 n - 1 ,且恰好有 n - 1 条路。0 是首都。给你一个二维整数数组 roads ,其中 roads[i] = [ai, bi] ,表示城市 ai 和 bi 之间有一条 双向路 。
每个城市里有一个代表,他们都要去首都参加一个会议。
每座城市里有一辆车。给你一个整数 seats 表示每辆车里面座位的数目。
城市里的代表可以选择乘坐所在城市的车,或者乘坐其他城市的车。相邻城市之间一辆车的油耗是一升汽油。
请你返回到达首都最少需要多少升汽油。
示例 1:
输入:roads = [[0,1],[0,2],[0,3]], seats = 5
输出:3
解释:
- 代表 1 直接到达首都,消耗 1 升汽油。
- 代表 2 直接到达首都,消耗 1 升汽油。
- 代表 3 直接到达首都,消耗 1 升汽油。
最少消耗 3 升汽油。
class Solution {
public:
long long ans;
int h[100010], ne[200010], e[200010], idx;
int d;
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int dfs(int u, int fa){
int s = 1;
for(int i = h[u]; i != -1; i = ne[i]){
int j = e[i];
if(j == fa) continue;
int t = dfs(j, u);
ans += (t + d - 1) / d; // 向上取整
s += t;
}
return s;
}
long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
d = seats;
memset(h, -1, sizeof h);
for(auto x : roads){
add(x[0], x[1]), add(x[1], x[0]);
}
dfs(0, -1);
return ans;
}
};