# 2477. Minimum Fuel Cost to Report to the Capital

• Time: $O(n)$
• Space: $O(n)$
  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 class Solution { public: long long minimumFuelCost(vector>& roads, int seats) { long long ans = 0; vector> tree(roads.size() + 1); for (const vector& road : roads) { const int u = road[0]; const int v = road[1]; tree[u].push_back(v); tree[v].push_back(u); } dfs(tree, 0, -1, seats, ans); return ans; } private: int dfs(const vector>& tree, int u, int prev, int seats, long long& ans) { int people = 1; for (const int v : tree[u]) { if (v == prev) continue; people += dfs(tree, v, u, seats, ans); } if (u > 0) // # of cars needed = ceil(people / seats) ans += (people + seats - 1) / seats; return people; } }; 
  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 class Solution { public long minimumFuelCost(int[][] roads, int seats) { List[] tree = new List[roads.length + 1]; for (int i = 0; i < tree.length; ++i) tree[i] = new ArrayList<>(); for (int[] road : roads) { final int u = road[0]; final int v = road[1]; tree[u].add(v); tree[v].add(u); } dfs(tree, 0, -1, seats); return ans; } private long ans = 0; private int dfs(List[] tree, int u, int prev, int seats) { int people = 1; for (final int v : tree[u]) { if (v == prev) continue; people += dfs(tree, v, u, seats); } if (u > 0) // # of cars needed = ceil(people / seats) ans += (people + seats - 1) / seats; return people; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution: def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int: ans = 0 tree = [[] for _ in range(len(roads) + 1)] for u, v in roads: tree[u].append(v) tree[v].append(u) def dfs(u: int, prev: int) -> int: nonlocal ans people = 1 for v in tree[u]: if v == prev: continue people += dfs(v, u) if u > 0: # number of cars needed ans += int(math.ceil(people / seats)) return people dfs(0, -1) return ans