# Minimum Fuel Cost to Report to the Capital
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/minimum-fuel-cost-to-report-to-the-capital)
Canonical: https://scaleengineer.com/dsa/problems/minimum-fuel-cost-to-report-to-the-capital
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Graph
**Companies:** [American Express](https://scaleengineer.com/companies/american-express), [DRW](https://scaleengineer.com/companies/drw)
---
## Problem
There is a tree (i.e., a connected, undirected graph with no cycles) structure country network consisting of `n` cities numbered from `0` to `n - 1` and exactly `n - 1` roads. The capital city is city `0`. You are given a 2D integer array `roads` where `roads[i] = [ai, bi]` denotes that there exists a **bidirectional road** connecting cities `ai` and `bi`.

There is a meeting for the representatives of each city. The meeting is in the capital city.

There is a car in each city. You are given an integer `seats` that indicates the number of seats in each car.

A representative can use the car in their city to travel or change the car and ride with another representative. The cost of traveling between two cities is one liter of fuel.

Return _the minimum number of liters of fuel to reach the capital city_.

**Example 1:**

![](https://assets.glich.co/dsa/minimum-fuel-cost-to-report-to-the-capital/image0.png) 

**Input:** roads = [[0,1],[0,2],[0,3]], seats = 5
**Output:** 3
**Explanation:** 
- Representative1 goes directly to the capital with 1 liter of fuel.
- Representative2 goes directly to the capital with 1 liter of fuel.
- Representative3 goes directly to the capital with 1 liter of fuel.
It costs 3 liters of fuel at minimum. 
It can be proven that 3 is the minimum number of liters of fuel needed.

**Example 2:**

![](https://assets.glich.co/dsa/minimum-fuel-cost-to-report-to-the-capital/image1.png) 

**Input:** roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats = 2
**Output:** 7
**Explanation:** 
- Representative2 goes directly to city 3 with 1 liter of fuel.
- Representative2 and representative3 go together to city 1 with 1 liter of fuel.
- Representative2 and representative3 go together to the capital with 1 liter of fuel.
- Representative1 goes directly to the capital with 1 liter of fuel.
- Representative5 goes directly to the capital with 1 liter of fuel.
- Representative6 goes directly to city 4 with 1 liter of fuel.
- Representative4 and representative6 go together to the capital with 1 liter of fuel.
It costs 7 liters of fuel at minimum. 
It can be proven that 7 is the minimum number of liters of fuel needed.

**Example 3:**

![](https://assets.glich.co/dsa/minimum-fuel-cost-to-report-to-the-capital/image2.png) 

**Input:** roads = [], seats = 1
**Output:** 0
**Explanation:** No representatives need to travel to the capital city.

**Constraints:**

* `1 <= n <= 105`
* `roads.length == n - 1`
* `roads[i].length == 2`
* `0 <= ai, bi < n`
* `ai != bi`
* `roads` represents a valid tree.
* `1 <= seats <= 105`

# Approaches
## Brute-Force by Iterating Through Edges
This approach calculates the total fuel cost by summing up the costs for each edge individually. The core idea is that for any edge connecting a child city to a parent city, the fuel required is determined by the number of representatives in the child's subtree. To find this number, this method iterates through each edge (or non-capital city) and performs a separate graph traversal to count the nodes in its subtree. This is a straightforward but inefficient way to solve the problem.
**Time:** O(N^2) in the worst case. A preliminary traversal to find parents takes O(N). Then, for each of the N-1 non-capital cities, we perform a traversal to count its subtree nodes. In a skewed tree (a path), this traversal can take up to O(N) time, leading to a total of O(N^2). · **Space:** O(N), where N is the number of cities. This is for storing the adjacency list, the parent array, and the recursion stack for the traversals.
**Pros:** Conceptually simple as it breaks the problem down into independent calculations for each edge.
**Cons:** Highly inefficient due to redundant computations. The size of a node's subtree is recalculated for each of its ancestors, leading to a quadratic time complexity.; More complex implementation with multiple nested traversals.
### Explanation
The fundamental principle is that the total fuel is the sum of fuel consumed on each road. The fuel for one road trip (between two adjacent cities) is 1 liter. To minimize fuel, we must minimize the number of car trips. For an edge `(u, v)` where `u` is the parent of `v` (closer to the capital 0), all representatives from the subtree of `v` must travel from `v` to `u`. If there are `k` representatives in `v`'s subtree, they need `ceil(k / seats)` cars to travel to `u`. This approach calculates `k` for each city `v` by running a dedicated traversal, which is computationally expensive.

```java
class Solution {
    private List<List<Integer>> adj; 
    private int[] parent;
    private int n;

    public long minimumFuelCost(int[][] roads, int seats) {
        n = roads.length + 1;
        if (n <= 1) {
            return 0;
        }

        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] road : roads) {
            adj.get(road[0]).add(road[1]);
            adj.get(road[1]).add(road[0]);
        }

        // Step 1: Find parents for all nodes relative to capital 0
        parent = new int[n];
        findParents();

        long totalFuel = 0;
        // Step 2: Iterate through each non-capital city
        for (int i = 1; i < n; i++) {
            // Step 3: Count people in subtree of i
            long peopleCount = countSubtreeNodes(i, parent[i]);
            // Step 4: Calculate fuel and add to total
            long cars = (peopleCount + seats - 1) / seats;
            totalFuel += cars;
        }

        return totalFuel;
    }

    private void findParents() {
        Queue<Integer> queue = new LinkedList<>();
        boolean[] visited = new boolean[n];
        queue.offer(0);
        visited[0] = true;
        parent[0] = -1;

        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    parent[v] = u;
                    queue.offer(v);
                }
            }
        }
    }

    private int countSubtreeNodes(int u, int p) {
        int count = 1; // Count the node itself
        for (int v : adj.get(u)) {
            if (v != p) { // Only go down the tree
                count += countSubtreeNodes(v, u);
            }
        }
        return count;
    }
}
```
### Algorithm
- Build an adjacency list for the tree.
- To easily identify parent-child relationships relative to the capital (node 0), perform a preliminary Breadth-First Search (BFS) or Depth-First Search (DFS) starting from node 0. This traversal computes the parent of each node in the tree rooted at the capital.
- Initialize a variable `totalFuel = 0`.
- Iterate through each city `i` from `1` to `n-1` (all non-capital cities).
- For each city `i`, calculate the size of the subtree rooted at `i`. This is done by a separate traversal (e.g., another DFS) starting from `i` that only explores its children and their descendants. This traversal counts the total number of nodes in the subtree.
- Let the subtree size be `peopleCount`. These are the representatives who must pass through the edge connecting city `i` to its parent.
- The fuel cost for this edge is the number of cars required, which is `ceil(peopleCount / seats)`. This can be calculated using integer arithmetic as `(peopleCount + seats - 1) / seats`.
- Add this fuel cost to `totalFuel`.
- After iterating through all non-capital cities, `totalFuel` will hold the minimum total fuel required.

## Iterative Approach with BFS from Leaves
A more efficient approach is to process the tree from the leaves inward towards the capital. This can be modeled as a topological sort. We start with the current leaves of the tree. For each leaf, we calculate the fuel needed to send its representatives to its parent. Then, we effectively 'prune' the leaf, passing its representative count to its parent. This might cause the parent to become a new leaf, which we then add to our set of nodes to process. This iterative process continues until all representatives reach the capital.
**Time:** O(N). Building the graph and degrees takes O(N). Each node is enqueued and processed once. The total work is proportional to the number of nodes and edges. · **Space:** O(N), where N is the number of cities. This space is used for the adjacency list, the `degree` array, the `representatives` array, and the queue, which can store up to O(N) nodes.
**Pros:** Efficient O(N) time complexity.; Being iterative, it avoids potential stack overflow issues on very deep trees.
**Cons:** The setup is slightly more involved than a direct DFS, as it requires managing node degrees and a queue explicitly.
### Explanation
This method avoids the re-computation of the brute-force approach by processing each node and edge just once. It's an iterative method that uses a queue to keep track of the leaves of the shrinking tree.

```java
class Solution {
    public long minimumFuelCost(int[][] roads, int seats) {
        int n = roads.length + 1;
        if (n <= 1) {
            return 0;
        }

        List<List<Integer>> adj = new ArrayList<>();
        int[] degree = new int[n];
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int[] road : roads) {
            adj.get(road[0]).add(road[1]);
            adj.get(road[1]).add(road[0]);
            degree[road[0]]++;
            degree[road[1]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        long[] representatives = new long[n];
        Arrays.fill(representatives, 1);

        for (int i = 1; i < n; i++) {
            if (degree[i] == 1) {
                queue.offer(i);
            }
        }

        long totalFuel = 0;
        while (!queue.isEmpty()) {
            int u = queue.poll();

            // Find the neighbor to move towards the capital
            int v = -1;
            for (int neighbor : adj.get(u)) {
                // In this algorithm, the neighbor with degree > 0 is the parent
                // (or will be processed later)
                if (degree[neighbor] > 0) { 
                    v = neighbor;
                    break;
                }
            }

            long cars = (representatives[u] + seats - 1) / seats;
            totalFuel += cars;

            // Move representatives to the parent node
            if (v != -1) {
                representatives[v] += representatives[u];
                degree[u]--; // Mark u as processed
                degree[v]--;
                if (degree[v] == 1 && v != 0) {
                    queue.offer(v);
                }
            }
        }

        return totalFuel;
    }
}
```
### Algorithm
- Build an adjacency list and an array to store the degree of each city.
- Initialize a queue for a Breadth-First Search (BFS) and add all initial leaf nodes (cities with degree 1). If the capital (city 0) is a leaf, do not add it to the queue, as it's our destination.
- Create an array `representatives` of size `n`, and initialize all its elements to 1.
- Initialize `totalFuel = 0`.
- Process nodes from the queue:
  - Dequeue a city `u`.
  - Find its only unprocessed neighbor `v`.
  - Calculate the fuel needed to move all representatives from `u` to `v`: `fuel = (representatives[u] + seats - 1) / seats`.
  - Add this `fuel` to `totalFuel`.
  - Aggregate the representatives at city `v`: `representatives[v] += representatives[u]`.
  - Decrement the degree of the neighbor `v`. If `v`'s degree becomes 1 and `v` is not the capital, it has become a new leaf in the remaining graph, so add it to the queue.
- Continue until the queue is empty, by which time all edges will have been processed. Return `totalFuel`.

## Optimal Single-Pass DFS from the Capital
This is arguably the most direct and elegant approach. It uses a single Depth-First Search (DFS) pass starting from the capital (city 0). The key is to use a post-order traversal pattern: for any given city, we first visit all its children subtrees, and on the way back up (after the recursive calls return), we have all the information we need. Specifically, the recursive call for a child city will return the total number of representatives in its subtree. With this count, we can calculate the fuel required for the edge connecting the child to the current city and add it to our total.
**Time:** O(N). The DFS algorithm visits each node and edge exactly once. · **Space:** O(N), where N is the number of cities. This space is required for the adjacency list and the recursion call stack. The depth of the recursion stack can be up to O(N) in the worst case of a skewed tree.
**Pros:** Highly efficient with O(N) time complexity.; The code is concise and the logic directly maps to the recursive structure of the problem.; It solves the problem in a single traversal of the graph.
**Cons:** For extremely deep trees (e.g., a path graph with N=10^5), a recursive solution might lead to a `StackOverflowError` in some programming environments, although this is often not an issue with modern systems and typical contest limits.
### Explanation
The DFS function traverses the tree and, for each node, computes the size of the subtree rooted at it. This size represents the number of people that need to be transported across the edge connecting this subtree to its parent. The total fuel is the sum of fuel costs for all such edges.

```java
class Solution {
    private long totalFuel;
    private List<List<Integer>> adj;
    private int seats;

    public long minimumFuelCost(int[][] roads, int seats) {
        int n = roads.length + 1;
        if (n <= 1) {
            return 0;
        }

        this.seats = seats;
        this.totalFuel = 0;
        this.adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int[] road : roads) {
            adj.get(road[0]).add(road[1]);
            adj.get(road[1]).add(road[0]);
        }

        dfs(0, -1);
        return totalFuel;
    }

    private long dfs(int u, int parent) {
        long representatives = 1;
        for (int v : adj.get(u)) {
            if (v == parent) {
                continue;
            }
            long representativesFromChild = dfs(v, u);
            representatives += representativesFromChild;
            
            // Calculate fuel for the edge (u, v)
            long cars = (representativesFromChild + seats - 1) / seats;
            totalFuel += cars;
        }
        return representatives;
    }
}
```
### Algorithm
- Build an adjacency list representation of the tree.
- Initialize a global or class-level variable `totalFuel = 0` of type `long`.
- Define a recursive Depth-First Search (DFS) function, `dfs(u, parent, seats, adj)`, which will return the number of representatives in the subtree rooted at `u`.
- Start the traversal from the capital: `dfs(0, -1, seats, adj)`. The `parent` parameter (`-1` for the root) prevents the traversal from going backward.
- Inside `dfs(u, parent)`:
  - Initialize `peopleInSubtree = 1` (for the representative in city `u`).
  - For each neighbor `v` of `u`:
    - If `v` is the `parent`, skip it.
    - Recursively call `dfs(v, u, ...)` to get the number of people from the child's subtree, `peopleFromChild`.
    - Add `peopleFromChild` to `peopleInSubtree`.
    - These `peopleFromChild` must travel from `v` to `u`. Calculate the fuel cost: `(peopleFromChild + seats - 1) / seats`.
    - Add this cost to the global `totalFuel`.
  - If `u` is not the capital (i.e., `u != 0`), return `peopleInSubtree`. If `u` is the capital, the return value is not strictly needed for the fuel calculation, but returning the total number of people is consistent.
- After the initial `dfs` call completes, `totalFuel` will contain the final answer.

# Solutions
### Java

```java
class Solution {
private
  List<Integer>[] g;
private
  int seats;
private
  long ans;
public
  long minimumFuelCost(int[][] roads, int seats) {
    int n = roads.length + 1;
    g = new List[n];
    Arrays.setAll(g, k->new ArrayList<>());
    this.seats = seats;
    for (var e : roads) {
      int a = e[0], b = e[1];
      g[a].add(b);
      g[b].add(a);
    }
    dfs(0, -1);
    return ans;
  }
private
  int dfs(int a, int fa) {
    int sz = 1;
    for (int b : g[a]) {
      if (b != fa) {
        int t = dfs(b, a);
        ans += (t + seats - 1) / seats;
        sz += t;
      }
    }
    return sz;
  }
}

```

### CPP

```cpp
class Solution { public: long long minimumFuelCost ( vector < vector < int >>& roads , int seats ) { int n = roads . size () + 1 ; vector < int > g [ n ]; for ( auto & e : roads ) { int a = e [ 0 ], b = e [ 1 ]; g [ a ]. emplace_back ( b ); g [ b ]. emplace_back ( a ); } long long ans = 0 ; function < int ( int , int ) > dfs = [ & ]( int a , int fa ) { int sz = 1 ; for ( int b : g [ a ]) { if ( b != fa ) { int t = dfs ( b , a ); ans += ( t + seats - 1 ) / seats ; sz += t ; } } return sz ; }; dfs ( 0 , - 1 ); return ans ; } };
```

### Python

```python
class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int: def dfs(a: int, fa: int) -> int: nonlocal ans sz = 1 for b in g[a]: if b != fa: t = dfs(b, a) ans += ceil(t / seats) sz += t return sz g = defaultdict(list) for a, b in roads: g[a]. append(b) g[b]. append(a) ans = 0 dfs(0, - 1) return ans

```