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

Description

The bidirectional roads in roads connect n = roads.length + 1 cities into a tree. Cities are labeled 0 through n - 1, and city 0 is the capital.

Each city has one representative and one car. Every car has seats seats, and each car uses one liter of fuel whenever it crosses a road. Representatives may share cars and transfer between cars at a city.

Return the minimum total fuel needed to bring all representatives to city 0. The representative already in the capital does not need to travel.

Example 1:

Minimum Fuel Cost to Report to the Capital, example 1: illustration of the example

Input: roads = [[0,1],[1,2],[2,3]]
seats = 2

Output: 4

Explanation: The representative from city 3 uses 1 liter to reach city 2. Those two representatives share a car to city 1 for 1 more liter. The three representatives now need two cars to cross from city 1 to city 0, costing 2 more liters. Total: 4.

Example 2:

Minimum Fuel Cost to Report to the Capital, example 2: illustration of the example

Input: roads = [[0,1],[0,2],[0,3]]
seats = 4

Output: 3

Explanation: Each noncapital city has its own road to city 0. Its representative must cross that road once, so three car trips cost 3 liters in total.

Example 3:

Minimum Fuel Cost to Report to the Capital, example 3: illustration of the example

Input: roads = []
seats = 3

Output: 0

Explanation: There is only city 0. Its representative is already at the meeting, so no fuel is needed.

Constraints:

n == roads.length + 1
1 <= n <= 100000
roads[i].length == 2
Each road joins two distinct city labels between 0 and n - 1.
The roads form a connected tree.
1 <= seats <= 100000

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Tree/Graph Representation - Understanding how to represent trees using adjacency lists and traversing undirected graphs
Depth First Search (DFS) - Ability to traverse trees recursively while tracking parent nodes to avoid revisiting
Ceiling Division - Knowing how to compute the ceiling of integer division (e.g., using (a + b - 1) / b or math.ceil)

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

Build an adjacency list from the given roads.
Run dfs starting from node 0, tracking the parent to avoid revisiting.
For each node, recursively gather passengers from all child subtrees.
After processing children, add the fuel cost for moving those passengers one edge closer to the capital: ceil(passengers / seats).
Return total passengers from the subtree (including the current node's representative).
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

public class Solution {
    private List<Integer>[] adj;
    private long res = 0;

    public long minimumFuelCost(int[][] roads, int seats) {
        int n = roads.length + 1;
        adj = new ArrayList[n];

        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>();
        }

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

        dfs(0, -1, seats);
        return res;
    }

    private int dfs(int node, int parent, int seats) {
        int passengers = 0;
        for (int child : adj[node]) {
            if (child != parent) {
                int p = dfs(child, node, seats);
                passengers += p;
                res += Math.ceil((double) p / seats);
            }
        }
        return passengers + 1;
    }
}

class Solution {
private:
    vector<vector<int>> adj;
    long long res = 0;

public:
    long long minimumFuelCost(vector<vector<int>>& roads, int seats) {
        int n = roads.size() + 1;
        adj.resize(n);

        for (auto& road : roads) {
            adj[road[0]].push_back(road[1]);
            adj[road[1]].push_back(road[0]);
        }

        dfs(0, -1, seats);
        return res;
    }

private:
    int dfs(int node, int parent, int seats) {
        int passengers = 0;
        for (int child : adj[node]) {
            if (child != parent) {
                int p = dfs(child, node, seats);
                passengers += p;
                res += ceil((double) p / seats);
            }
        }
        return passengers + 1;
    }
};

class Solution {
    /**
     * @param {number[][]} roads
     * @param {number} seats
     * @return {number}
     */
    minimumFuelCost(roads, seats) {
        const n = roads.length + 1;
        const adj = Array.from({ length: n }, () => []);
        let res = 0;

        for (const [src, dst] of roads) {
            adj[src].push(dst);
            adj[dst].push(src);
        }

        const dfs = (node, parent) => {
            let passengers = 0;
            for (const child of adj[node]) {
                if (child !== parent) {
                    let p = dfs(child, node);
                    passengers += p;
                    res += Math.ceil(p / seats);
                }
            }
            return passengers + 1;
        };

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

public class Solution {
    private List<int>[] adj;
    private long res = 0;

    public long MinimumFuelCost(int[][] roads, int seats) {
        int n = roads.Length + 1;
        adj = new List<int>[n];

        for (int i = 0; i < n; i++) {
            adj[i] = new List<int>();
        }

        foreach (var road in roads) {
            adj[road[0]].Add(road[1]);
            adj[road[1]].Add(road[0]);
        }

        Dfs(0, -1, seats);
        return res;
    }

    private int Dfs(int node, int parent, int seats) {
        int passengers = 0;
        foreach (int child in adj[node]) {
            if (child != parent) {
                int p = Dfs(child, node, seats);
                passengers += p;
                res += (int)Math.Ceiling((double)p / seats);
            }
        }
        return passengers + 1;
    }
}

func minimumFuelCost(roads [][]int, seats int) int64 {
    n := len(roads) + 1
    adj := make([][]int, n)
    for i := range adj {
        adj[i] = []int{}
    }

    for _, road := range roads {
        adj[road[0]] = append(adj[road[0]], road[1])
        adj[road[1]] = append(adj[road[1]], road[0])
    }

    var res int64 = 0

    var dfs func(node, parent int) int
    dfs = func(node, parent int) int {
        passengers := 0
        for _, child := range adj[node] {
            if child != parent {
                p := dfs(child, node)
                passengers += p
                res += int64((p + seats - 1) / seats)
            }
        }
        return passengers + 1
    }

    dfs(0, -1)
    return res
}

class Solution {
    private lateinit var adj: Array<MutableList<Int>>
    private var res = 0L

    fun minimumFuelCost(roads: Array<IntArray>, seats: Int): Long {
        val n = roads.size + 1
        adj = Array(n) { mutableListOf() }

        for (road in roads) {
            adj[road[0]].add(road[1])
            adj[road[1]].add(road[0])
        }

        dfs(0, -1, seats)
        return res
    }

    private fun dfs(node: Int, parent: Int, seats: Int): Int {
        var passengers = 0
        for (child in adj[node]) {
            if (child != parent) {
                val p = dfs(child, node, seats)
                passengers += p
                res += kotlin.math.ceil(p.toDouble() / seats).toLong()
            }
        }
        return passengers + 1
    }
}

class Solution {
    func minimumFuelCost(_ roads: [[Int]], _ seats: Int) -> Int {
        let n = roads.count + 1
        var adj = [[Int]](repeating: [], count: n)
        var res = 0

        for road in roads {
            adj[road[0]].append(road[1])
            adj[road[1]].append(road[0])
        }

        func dfs(_ node: Int, _ parent: Int) -> Int {
            var passengers = 0
            for child in adj[node] {
                if child != parent {
                    let p = dfs(child, node)
                    passengers += p
                    res += (p + seats - 1) / seats
                }
            }
            return passengers + 1
        }

        dfs(0, -1)
        return res
    }
}

impl Solution {
    pub fn minimum_fuel_cost(roads: Vec<Vec<i32>>, seats: i32) -> i64 {
        let n = roads.len() + 1;
        let mut adj = vec![vec![]; n];

        for road in &roads {
            adj[road[0] as usize].push(road[1] as usize);
            adj[road[1] as usize].push(road[0] as usize);
        }

        let mut res: i64 = 0;
        Self::dfs(0, usize::MAX, seats as i64, &adj, &mut res);
        res
    }

    fn dfs(
        node: usize,
        parent: usize,
        seats: i64,
        adj: &Vec<Vec<usize>>,
        res: &mut i64,
    ) -> i64 {
        let mut passengers: i64 = 0;
        for &child in &adj[node] {
            if child != parent {
                let p = Self::dfs(child, node, seats, adj, res);
                passengers += p;
                *res += (p + seats - 1) / seats;
            }
        }
        passengers + 1
    }
}

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

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

public class Solution {
    public long minimumFuelCost(int[][] roads, int seats) {
        int n = roads.length + 1;
        List<Integer>[] adj = new ArrayList[n];
        int[] indegree = new int[n];
        int[] passengers = new int[n];
        Arrays.fill(passengers, 1);
        long res = 0;

        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();

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

        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i < n; i++) {
            if (indegree[i] == 1) q.offer(i);
        }

        while (!q.isEmpty()) {
            int node = q.poll();
            res += (int) Math.ceil((double) passengers[node] / seats);
            for (int parent : adj[node]) {
                if (--indegree[parent] == 1 && parent != 0) q.offer(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;
    }
};

class Solution {
    /**
     * @param {number[][]} roads
     * @param {number} seats
     * @return {number}
     */
    minimumFuelCost(roads, seats) {
        const n = roads.length + 1;
        const adj = Array.from({ length: n }, () => []);
        const indegree = new Array(n).fill(0);
        const passengers = new Array(n).fill(1);
        let res = 0;

        for (const [src, dst] of roads) {
            adj[src].push(dst);
            adj[dst].push(src);
            indegree[src] += 1;
            indegree[dst] += 1;
        }

        const q = new Queue();
        for (let i = 1; i < n; i++) {
            if (indegree[i] === 1) q.push(i);
        }

        while (!q.isEmpty()) {
            const node = q.pop();
            res += Math.ceil(passengers[node] / seats);
            for (const parent of adj[node]) {
                if (--indegree[parent] === 1 && parent !== 0) q.push(parent);
                passengers[parent] += passengers[node];
            }
        }

        return res;
    }
}

public class Solution {
    public long MinimumFuelCost(int[][] roads, int seats) {
        int n = roads.Length + 1;
        List<int>[] adj = new List<int>[n];
        int[] indegree = new int[n];
        int[] passengers = new int[n];
        Array.Fill(passengers, 1);
        long res = 0;

        for (int i = 0; i < n; i++) adj[i] = new List<int>();

        foreach (var road in roads) {
            int src = road[0], dst = road[1];
            adj[src].Add(dst);
            adj[dst].Add(src);
            indegree[src]++;
            indegree[dst]++;
        }

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

        while (q.Count > 0) {
            int node = q.Dequeue();
            res += (int)Math.Ceiling((double)passengers[node] / seats);
            foreach (int parent in adj[node]) {
                if (--indegree[parent] == 1 && parent != 0) q.Enqueue(parent);
                passengers[parent] += passengers[node];
            }
        }

        return res;
    }
}

func minimumFuelCost(roads [][]int, seats int) int64 {
    n := len(roads) + 1
    adj := make([][]int, n)
    indegree := make([]int, n)
    passengers := make([]int, n)
    for i := range passengers {
        passengers[i] = 1
    }
    var res int64 = 0

    for i := range adj {
        adj[i] = []int{}
    }

    for _, road := range roads {
        src, dst := road[0], road[1]
        adj[src] = append(adj[src], dst)
        adj[dst] = append(adj[dst], src)
        indegree[src]++
        indegree[dst]++
    }

    q := []int{}
    for i := 1; i < n; i++ {
        if indegree[i] == 1 {
            q = append(q, i)
        }
    }

    for len(q) > 0 {
        node := q[0]
        q = q[1:]
        res += int64((passengers[node] + seats - 1) / seats)
        for _, parent := range adj[node] {
            indegree[parent]--
            if indegree[parent] == 1 && parent != 0 {
                q = append(q, parent)
            }
            passengers[parent] += passengers[node]
        }
    }

    return res
}

class Solution {
    fun minimumFuelCost(roads: Array<IntArray>, seats: Int): Long {
        val n = roads.size + 1
        val adj = Array(n) { mutableListOf<Int>() }
        val indegree = IntArray(n)
        val passengers = IntArray(n) { 1 }
        var res = 0L

        for (road in roads) {
            val (src, dst) = road
            adj[src].add(dst)
            adj[dst].add(src)
            indegree[src]++
            indegree[dst]++
        }

        val q = ArrayDeque<Int>()
        for (i in 1 until n) {
            if (indegree[i] == 1) q.add(i)
        }

        while (q.isNotEmpty()) {
            val node = q.removeFirst()
            res += kotlin.math.ceil(passengers[node].toDouble() / seats).toLong()
            for (parent in adj[node]) {
                if (--indegree[parent] == 1 && parent != 0) q.add(parent)
                passengers[parent] += passengers[node]
            }
        }

        return res
    }
}

class Solution {
    func minimumFuelCost(_ roads: [[Int]], _ seats: Int) -> Int {
        let n = roads.count + 1
        var adj = [[Int]](repeating: [], count: n)
        var indegree = [Int](repeating: 0, count: n)
        var passengers = [Int](repeating: 1, count: n)
        var res = 0

        for road in roads {
            let src = road[0], dst = road[1]
            adj[src].append(dst)
            adj[dst].append(src)
            indegree[src] += 1
            indegree[dst] += 1
        }

        var q = [Int]()
        for i in 1..<n {
            if indegree[i] == 1 { q.append(i) }
        }

        while !q.isEmpty {
            let node = q.removeFirst()
            res += (passengers[node] + seats - 1) / seats
            for parent in adj[node] {
                indegree[parent] -= 1
                if indegree[parent] == 1 && parent != 0 { q.append(parent) }
                passengers[parent] += passengers[node]
            }
        }

        return res
    }
}

impl Solution {
    pub fn minimum_fuel_cost(roads: Vec<Vec<i32>>, seats: i32) -> i64 {
        let n = roads.len() + 1;
        let mut adj = vec![vec![]; n];
        let mut indegree = vec![0i32; n];
        let mut passengers = vec![1i64; n];
        let mut res: i64 = 0;
        let seats = seats as i64;

        for road in &roads {
            let (src, dst) = (road[0] as usize, road[1] as usize);
            adj[src].push(dst);
            adj[dst].push(src);
            indegree[src] += 1;
            indegree[dst] += 1;
        }

        let mut q = VecDeque::new();
        for i in 1..n {
            if indegree[i] == 1 {
                q.push_back(i);
            }
        }

        while let Some(node) = q.pop_front() {
            res += (passengers[node] + seats - 1) / seats;
            for &parent in &adj[node].clone() {
                indegree[parent] -= 1;
                if indegree[parent] == 1 && parent != 0 {
                    q.push_back(parent);
                }
                passengers[parent] += passengers[node];
            }
        }

        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.