2477. Minimum Fuel Cost to Report to the Capital - Explanation

Problem Link

1. Depth First Search

Intuition

Think of the tree as a network of cities where everyone needs to travel to the capital (node 0). Since the tree structure means there's only one path from any city to the capital, we can work backwards from the leaves.

The key insight is that as we move toward the capital, passengers accumulate. At each node, we collect all the people from its subtree, and the number of cars needed to transport them equals the ceiling of passengers divided by seats. By using dfs to traverse from leaves to the root, we can count passengers bottom-up and calculate fuel costs as people flow toward the capital.

Algorithm

1. Build an adjacency list from the given roads.
2. Run dfs starting from node 0, tracking the parent to avoid revisiting.
3. For each node, recursively gather passengers from all child subtrees.
4. After processing children, add the fuel cost for moving those passengers one edge closer to the capital: ceil(passengers / seats).
5. Return total passengers from the subtree (including the current node's representative).
6. The accumulated fuel cost across all edges gives the answer.

class Solution:
    def minimumFuelCost(self, roads: list[list[int]], seats: int) -> int:
        adj = defaultdict(list)
        for src, dst in roads:
            adj[src].append(dst)
            adj[dst].append(src)

        res = 0
        def dfs(node, parent):
            nonlocal res
            passengers = 0
            for child in adj[node]:
                if child != parent:
                    p = dfs(child, node)
                    passengers += p
                    res += ceil(p / seats)
            return passengers + 1

        dfs(0, -1)
        return res

Time & Space Complexity

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

---

2. Topological Sort (Kahn's Algorithm)

Intuition

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.

Algorithm

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.

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

Time & Space Complexity

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

---

Common Pitfalls

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.