⚡Flashcard Drill➔
NeetCode #588LC-2477MediumGraphs
← Back to All Problems

#588 · #2477 · Minimum Fuel Cost to Report to the Capital(到达首都的最少油耗)

📌 Problem Statement & Constraints

There is a tree of n cities with city 0 as the capital. roads[i] = [a, b] is an undirected road. Each city has one representative, and each car has seats seats. Representatives travel toward the capital, and cars can share seats only when travelling together. Return the minimum total fuel cost, where each unit of distance costs 1 litre. Constraints: 1 <= n <= 10^5, 1 <= seats <= 10^5.

💡 Core Algorithmic Approaches

  1. Every edge on the path from a subtree to the capital must be traversed by exactly the cars needed to carry that subtree's representatives.
  2. So for each node, count the representatives in its subtree; the cars needed are ceil(people / seats).
  3. Add that to the total for the edge above the node.
  4. A post-order DFS computes all subtree counts in one pass.

💻 Benchmark Python3 Implementation

class Solution:
    def minimumFuelCost(self, roads: List[List[int]], seats: int) -> int:
        from collections import defaultdict
        g = defaultdict(list)
        for a, b in roads:
            g[a].append(b)
            g[b].append(a)

        self.fuel = 0

        def dfs(node: int, parent: int) -> int:
            people = 1                     # this city's own representative
            for nxt in g[node]:
                if nxt == parent:
                    continue
                people += dfs(nxt, node)   # gather the subtree
            if node != 0:                  # the edge to the parent must be paid
                self.fuel += (people + seats - 1) // seats   # ceiling
            return people

        dfs(0, -1)
        return self.fuel

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each node and edge is visited once.
💾 Space Complexity
O(n) for the adjacency list plus the recursion depth.

⚠️ Interview Pitfalls & Follow-ups

  • Using people // seats: the ceiling is required, since every representative must be seated.
  • Charging fuel for the capital's own edge: city 0 has no parent.
  • Forgetting the parent guard: the DFS would loop on the undirected tree.
  • Trying to route cars individually: the aggregation by subtree is what makes it linear.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems