Minimum Fuel Cost to Report to the Capital

medium graph dfs tree

Problem

There are n cities numbered 0 to n-1 connected by n-1 two-way roads that form a tree, with city 0 as the capital. Every city has exactly one representative who must travel to the capital. The roads array lists each road as a pair of connected cities. Each car holds seats people, and a car burns one liter of fuel for each road it drives along. Representatives may share cars when their routes overlap. Return the minimum liters of fuel needed for everyone to reach city 0.

Inputroads = [[0,1],[0,2],[0,3]], seats = 5

Output3

Cities 1, 2 and 3 each send one representative straight to 0 along one road, burning 1 liter per road: 1 + 1 + 1 = 3.

roads (e.g. "0,1; 0,2; 0,3")

seats

import math
def minimum_fuel_cost(roads, seats):
    n = len(roads) + 1
    adj = [[] for _ in range(n)]
    for a, b in roads:
        adj[a].append(b)
        adj[b].append(a)
    fuel = 0
    def dfs(u, parent):
        nonlocal fuel
        people = 1
        for v in adj[u]:
            if v != parent:
                people += dfs(v, u)
        if u != 0:
            fuel += math.ceil(people / seats)
        return people
    dfs(0, -1)
    return fuel

function minimumFuelCost(roads, seats) {
  const n = roads.length + 1;
  const adj = Array.from({ length: n }, () => []);
  for (const [a, b] of roads) {
    adj[a].push(b);
    adj[b].push(a);
  }
  let fuel = 0;
  function dfs(u, parent) {
    let people = 1;
    for (const v of adj[u]) {
      if (v !== parent) people += dfs(v, u);
    }
    if (u !== 0) fuel += Math.ceil(people / seats);
    return people;
  }
  dfs(0, -1);
  return fuel;
}

class Solution {
    long fuel;
    List<Integer>[] adj;
    public long minimumFuelCost(int[][] roads, int seats) {
        int n = roads.length + 1;
        adj = new List[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int[] r : roads) {
            adj[r[0]].add(r[1]);
            adj[r[1]].add(r[0]);
        }
        fuel = 0;
        dfs(0, -1, seats);
        return fuel;
    }
    private long dfs(int u, int parent, int seats) {
        long people = 1;
        for (int v : adj[u]) {
            if (v != parent) people += dfs(v, u, seats);
        }
        if (u != 0) fuel += (people + seats - 1) / seats;
        return people;
    }
}

long long fuel_;
vector<vector<int>> adj_;
long long dfs(int u, int parent, int seats) {
    long long people = 1;
    for (int v : adj_[u]) {
        if (v != parent) people += dfs(v, u, seats);
    }
    if (u != 0) fuel_ += (people + seats - 1) / seats;
    return people;
}
long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
    int n = roads.size() + 1;
    adj_.assign(n, {});
    for (auto& r : roads) {
        adj_[r[0]].push_back(r[1]);
        adj_[r[1]].push_back(r[0]);
    }
    fuel_ = 0;
    dfs(0, -1, seats);
    return fuel_;
}

Explanation

The cities form a tree rooted at the capital, city 0. Because a tree has exactly one path between any two cities, every representative's route to the capital is fixed — there are no choices to make about which way to go. The only thing we optimize is car sharing: representatives whose paths overlap should pool into the same cars.

Think about a single road, the edge between a city and its parent (the parent being one step closer to 0). Every representative living in the subtree hanging below that city must cross this exact road to get out. If people representatives need to cross and each car holds seats, then we need ceil(people / seats) cars, and each car burns 1 liter driving that one road. So the fuel charged to that edge is simply ceil(people / seats).

To know how many people cross each edge, we run a post-order DFS from the capital. Each city counts as 1 person (its own representative) plus the totals returned by all of its children. After summing the subtree, every non-capital city adds ceil(subtreeTotal / seats) to the running fuel — that is the cost of driving its outgoing road toward the parent.

Example: roads = [[0,1],[0,2],[0,3]], seats = 5. Cities 1, 2 and 3 are leaves, each with a subtree total of 1. Each pays ceil(1 / 5) = 1 liter to drive its single road into the capital, so the total is 1 + 1 + 1 = 3.

Since the DFS visits every city and every edge exactly once, the whole computation is a single linear pass over the tree.

Time: O(n) Space: O(n)