Minimum Fuel Cost to Report to the Capital — Medium Problem & Solution

A country has n cities numbered 0 … n - 1 joined by n - 1 bidirectional roads, forming a tree.

Difficulty: Medium
Topics: Breadth-First Search, Depth-First Search, Graph, Trees
Asked at: Amazon, Google, Uber
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A country has n cities numbered 0 … n - 1 joined by n - 1 bidirectional roads, forming a tree. City 0 is the capital, and every other city has one representative who must reach it.

Each representative starts with a car that seats seats people. A car burns one litre of fuel per road it drives, and representatives who meet in a city may share a car — as long as no car carries more than seats people. Return the minimum litres needed for everyone to reach the capital.

Example 1

Input: roads = [[0,1],[0,2],[0,3]], seats = 5
Output: 3
Explanation: Three representatives each drive one road.

Example 2

Input: roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats = 2
Output: 7

Example 3

Input: roads = [], seats = 1
Output: 0
Explanation: Only the capital exists.

Constraints

1 <= n <= 1000
roads.length == n - 1
roads[i].length == 2
0 <= roads[i][0], roads[i][1] < n
roads represents a valid tree
1 <= seats <= 100

How to solve Minimum Fuel Cost to Report to the Capital

Root the tree at the capital. The edge above a node is crossed by exactly the people in its subtree, and ferrying p people across one road costs ceil(p / seats) litres. Sum that over every edge.

Approach

Build the tree and record a traversal order with each node's parent.
Walk the order backwards so children are finished before their parent, accumulating subtree sizes.
For each non-root node add ceil(size / seats) to the answer.

Why it works

The edges decouple completely because the graph is a tree: there is exactly one road out of each subtree, so its traffic is fixed at the subtree's population no matter how the cars are arranged. Once traffic is fixed, filling cars to capacity is optimal on every edge independently, which is why a greedy sum over edges is exact and no search is needed.

Complexity

Time — O(n)
Space — O(n)

Pitfalls

The root has no edge above it and contributes nothing.
Use (size + seats - 1) / seats rather than floating-point division.
An iterative traversal avoids a deep recursion on a path-shaped tree.

Reference solution

Python

from typing import List

def minimumFuelCost(roads: List[List[int]], seats: int) -> int:
    n = len(roads) + 1
    adj = [[] for _ in range(n)]
    for u, v in roads:
        adj[u].append(v)
        adj[v].append(u)
    parent = [-1] * n
    order = []
    seen = [False] * n
    seen[0] = True
    stack = [0]
    while stack:
        u = stack.pop()
        order.append(u)
        for v in adj[u]:
            if seen[v]:
                continue
            seen[v] = True
            parent[v] = u
            stack.append(v)
    cnt = [1] * n
    fuel = 0
    for i in range(len(order) - 1, 0, -1):
        u = order[i]
        cnt[parent[u]] += cnt[u]
        fuel += (cnt[u] + seats - 1) // seats
    return fuel

JavaScript

var minimumFuelCost = function(roads, seats) {
    var n = roads.length + 1, i;
    var adj = [];
    for (i = 0; i < n; i++) adj.push([]);
    for (i = 0; i < roads.length; i++) {
        adj[roads[i][0]].push(roads[i][1]);
        adj[roads[i][1]].push(roads[i][0]);
    }
    var parent = [], seen = [];
    for (i = 0; i < n; i++) { parent.push(-1); seen.push(false); }
    var order = [];
    var stack = [0];
    seen[0] = true;
    while (stack.length > 0) {
        var u = stack.pop();
        order.push(u);
        for (i = 0; i < adj[u].length; i++) {
            var v = adj[u][i];
            if (seen[v]) continue;
            seen[v] = true;
            parent[v] = u;
            stack.push(v);
        }
    }
    var cnt = [];
    for (i = 0; i < n; i++) cnt.push(1);
    var fuel = 0;
    for (i = order.length - 1; i >= 1; i--) {
        var w = order[i];
        cnt[parent[w]] += cnt[w];
        fuel += Math.floor((cnt[w] + seats - 1) / seats);
    }
    return fuel;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 65 breadth-first search problems · the whole catalogue