1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
List<Integer>[] g;
int seats;
long ans;
public long minimumFuelCost(int[][] roads, int seats) {
this.seats = seats;
int n = roads.length + 1;
g = new List[n];
Arrays.setAll(g, k -> new ArrayList<>());
for (int[] road : roads) {
int a = road[0], b = road[1];
g[a].add(b);
g[b].add(a);
}
dfs(0, -1);
return ans;
}
private int dfs(int x, int pa) {
int size = 1;
for (int y : g[x]) {
if (y != pa) {
size += dfs(y, x);
}
}
if (x > 0) {
ans += (size - 1) / seats + 1;
}
return size;
}
}
|
wechat
