Minimum fuel cost to report to the capital

Tree Depth-First Search Breadth-First Search Graph Theory

64.9% acceptance

Feb 25, 2026

2313

There is a tree structure country network consisting of n cities numbered from 0 to n-1. The capital city is city 0. You are given roads[i] = [ai, bi]. There is a car in each city with seats seats. Representatives travel to the capital (city 0). Cost = fuel liters per edge. Group together to minimize fuel. Return minimum liters of fuel.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_fuel_cost(roads: Vec<Vec<i32>>, seats: i32) -> i64 {
    let n = roads.len() + 1;
    let mut adj: Vec<Vec<usize>> = vec![vec![]; n];
    for r in &roads {
      adj[r[0] as usize].push(r[1] as usize);
      adj[r[1] as usize].push(r[0] as usize);
    }
    let seats = seats as i64;
    let mut fuel = 0i64;

    fn dfs(u: usize, par: usize, adj: &Vec<Vec<usize>>, seats: i64, fuel: &mut i64) -> i64 {
      let mut size = 1i64;
      for &v in &adj[u] {
        if v != par {
          size += dfs(v, u, adj, seats, fuel);
        }
      }
      if u != 0 {
        *fuel += (size + seats - 1) / seats;
      }
      size
    }
    dfs(0, n, &adj, seats, &mut fuel);
    fuel
  }
}