Minimum Fuel Cost to Report to the Capital

Minimum Fuel Cost to Report to the Capital - Problem

There is a tree (i.e., a connected, undirected graph with no cycles) structure country network consisting of n cities numbered from 0 to n - 1 and exactly n - 1 roads. The capital city is city 0.

You are given a 2D integer array roads where roads[i] = [ai, bi] denotes that there exists a bidirectional road connecting cities ai and bi.

There is a meeting for the representatives of each city. The meeting is in the capital city.

There is a car in each city. You are given an integer seats that indicates the number of seats in each car.

A representative can use the car in their city to travel or change the car and ride with another representative. The cost of traveling between two cities is one liter of fuel.

Return the minimum number of liters of fuel to reach the capital city.

Input & Output

Example 1 — Basic Tree

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

› Output: 3

💡 Note: Capital 0 connects to cities 1, 2, 3. Each city sends 1 representative, each needs 1 car (since 1 ≤ 5 seats). Total: 1 + 1 + 1 = 3 liters.

Example 2 — Limited Seats

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

› Output: 7

💡 Note: Tree structure requires multiple cars due to seat limitation. Representatives share rides optimally based on subtree sizes and seat capacity.

Example 3 — Single Road

$ Input: roads = [[0,1]], seats = 1

› Output: 1

💡 Note: Only city 1 needs to send representative to capital 0. One car travels the single road: 1 liter.

Constraints

1 ≤ n ≤ 10⁵
roads.length == n - 1
roads[i].length == 2
0 ≤ a_i, b_i < n
a_i ≠ b_i
roads represents a valid tree
1 ≤ seats ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Tree structure with roads connecting cities, capital at city 0

Process

Calculate minimum cars needed for ride sharing to capital

Output

Total liters of fuel (one per car journey between cities)

Key Takeaway

🎯 Key Insight: Use DFS to count people in each subtree and calculate minimum cars needed per edge

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is to use DFS to calculate how many people need to travel from each subtree toward the capital, then determine the minimum number of cars needed based on seat capacity. The optimal approach traverses the tree once, computing ⌈people_count / seats⌉ cars for each edge. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ DFS with Ride Sharing	O(n)	O(n)	Optimal DFS solution that calculates minimum fuel by sharing rides efficiently
Brute Force DFS	O(n²)	O(n)	Simple DFS without optimization, each person travels separately

DFS with Ride Sharing — Algorithm Steps

Step 1: Build adjacency list from roads
Step 2: DFS from capital, calculating subtree sizes
Step 3: For each edge, calculate minimum cars needed
Step 4: Sum fuel costs for all edges

Visualization

Tap to expand

Step-by-Step Walkthrough

DFS Traversal

Visit nodes from leaves to root, counting people in subtrees

Calculate Cars

For each edge, compute minimum cars needed based on people count

Sum Fuel

Add up car counts for all edges to get total fuel

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_CITIES 1000

int graph[MAX_CITIES][MAX_CITIES];
int graphSize[MAX_CITIES];
long long totalFuel = 0;

int dfs(int node, int parent, int seats) {
    // Count people in this subtree (including this node)
    int peopleCount = 1;
    
    // Visit all children
    for (int i = 0; i < graphSize[node]; i++) {
        int neighbor = graph[node][i];
        if (neighbor != parent) {
            int childPeople = dfs(neighbor, node, seats);
            peopleCount += childPeople;
            
            // Calculate minimum cars needed for this edge
            int carsNeeded = (childPeople + seats - 1) / seats; // Ceiling division
            totalFuel += carsNeeded;
        }
    }
    
    return peopleCount;
}

long long solution(int roads[][2], int roadsSize, int seats) {
    if (roadsSize == 0) return 0;
    
    // Initialize graph
    memset(graphSize, 0, sizeof(graphSize));
    
    // Build adjacency list
    for (int i = 0; i < roadsSize; i++) {
        int a = roads[i][0], b = roads[i][1];
        graph[a][graphSize[a]++] = b;
        graph[b][graphSize[b]++] = a;
    }
    
    totalFuel = 0;
    
    // Start DFS from capital (node 0)
    dfs(0, -1, seats);
    
    return totalFuel;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse roads array
    int roads[500][2];
    int roadsSize = 0;
    
    if (strcmp(line, "[]\n") != 0) {
        char* ptr = line + 1;
        while (*ptr && *ptr != ']') {
            if (*ptr == '[') {
                ptr++;
                roads[roadsSize][0] = atoi(ptr);
                while (*ptr && *ptr != ',') ptr++;
                ptr++;
                roads[roadsSize][1] = atoi(ptr);
                roadsSize++;
                while (*ptr && *ptr != ']') ptr++;
                ptr++;
            } else {
                ptr++;
            }
        }
    }
    
    int seats;
    scanf("%d", &seats);
    
    printf("%lld\n", solution(roads, roadsSize, seats));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single DFS traversal visits each node and edge exactly once

✓ Linear Growth

Space Complexity

O(n)

Adjacency list storage and recursion stack depth up to tree height

⚡ Linearithmic Space

35.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS with Ride Sharing — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler