Minimum Fuel Cost to Report to the Capital

How it works

Instead of recursion, we can process the tree level by level starting from the leaf nodes. Leaves have only one connection, so we identify them by their degree. As each leaf "sends" its passengers toward the capital, we remove it from consideration and check if its neighbor becomes a new leaf.

This approach simulates the natural flow of people gathering and moving inward. Each time a node is processed, we calculate how many cars are needed to transport its passengers one step closer to the root.

Steps

1. Build an adjacency list and track the degree (number of edges) for each node.
2. Initialize a passengers array where each node starts with 1 (itself).
3. Add all nodes with degree 1 (except node 0) to the queue as initial leaves.
4. Process the queue: for each leaf, add ceil(passengers / seats) to the total fuel.
5. Transfer the leaf's passengers to its neighbor and decrement the neighbor's degree.
6. If the neighbor becomes a leaf (degree 1) and is not the capital, add it to the queue.
7. Return the total fuel cost.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Counting Fuel for the Capital Node

The capital (node 0) does not need to travel anywhere, so you should not add fuel cost for passengers arriving at node 0. A common mistake is calculating ceil(passengers / seats) for the capital itself, which incorrectly inflates the total fuel cost.

Incorrect Ceiling Division

When calculating cars needed, you need ceil(passengers / seats). Integer division truncates, so 7 / 3 = 2 instead of the correct 3. Use (passengers + seats - 1) / seats or a ceiling function to get the correct result. Floating-point division with casting can also introduce precision errors.

Revisiting the Parent in DFS

Since the graph is undirected, the adjacency list includes edges in both directions. When traversing with DFS, you must skip the parent node to avoid infinite recursion. Forgetting to pass and check the parent parameter causes stack overflow or incorrect passenger counts.

from collections import deque
import math

class Solution:
    def minimumFuelCost(self, roads: list[list[int]], seats: int) -> int:
        n = len(roads) + 1
        adj = [[] for _ in range(n)]
        indegree = [0] * n
        passengers = [1] * n
        res = 0

        for src, dst in roads:
            adj[src].append(dst)
            adj[dst].append(src)
            indegree[src] += 1
            indegree[dst] += 1

        q = deque()
        for i in range(1, n):
            if indegree[i] == 1:
                q.append(i)

        while q:
            node = q.popleft()
            res += math.ceil(passengers[node] / seats)
            for parent in adj[node]:
                indegree[parent] -= 1
                if indegree[parent] == 1 and parent != 0:
                    q.append(parent)
                passengers[parent] += passengers[node]

        return res

class Solution {
public:
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        int n = roads.size() + 1;
        vector<vector<int>> adj(n);
        vector<int> indegree(n, 0), passengers(n, 1);
        long long res = 0;

        for (auto& road : roads) {
            int src = road[0], dst = road[1];
            adj[src].push_back(dst);
            adj[dst].push_back(src);
            indegree[src]++;
            indegree[dst]++;
        }

        queue<int> q;
        for (int i = 1; i < n; i++) {
            if (indegree[i] == 1) q.push(i);
        }

        while (!q.empty()) {
            int node = q.front();q.pop();
            res += ceil((double) passengers[node] / seats);
            for (int parent : adj[node]) {
                if (--indegree[parent] == 1 && parent != 0) q.push(parent);
                passengers[parent] += passengers[node];
            }
        }

        return res;
    }
};