Practice/Amazon/Leetcode 2477. Minimum Fuel Cost to Report to the Capital

Leetcode 2477. Minimum Fuel Cost to Report to the Capital

CodingOptional

Problem

You are coordinating a transportation network across multiple cities connected by bidirectional roads forming a tree structure. City 0 is the central hub where an important meeting will take place. Each city (including city 0) has exactly one representative who needs to attend the meeting.

Representatives can share vehicles that have a fixed seating capacity. When traveling from one city to an adjacent city along a road, the vehicle consumes exactly 1 unit of fuel regardless of how many passengers are inside (up to the capacity limit).

Your task is to determine the minimum total fuel consumption needed to transport all representatives from their home cities to city 0.

Requirements

1. Calculate the total fuel units consumed across all vehicle trips
2. Optimize carpooling by filling vehicles up to their seating capacity
3. Handle the tree structure where city 0 is the root
4. Account for representatives from all cities aggregating as they travel toward the hub

Constraints

• 1 ≤ n ≤ 100,000 (number of cities)
• roads.length == n - 1
• roads[i] represents a bidirectional connection between two cities
• The roads form a tree (connected, acyclic graph)
• 1 ≤ seats ≤ 100,000
• City 0 is always the destination hub
• Time complexity should be O(n)
• Space complexity should be O(n)

Examples

Example 1:

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

• City 2 has 1 representative who travels to city 1 (1 fuel)
• City 3 has 1 representative who travels to city 1 (1 fuel)
• City 1 now has 3 representatives (its own + 2 from children)
• They need ceil(3/2) = 2 vehicles to travel to city 0 (2 fuel)
• Total: 1 + 1 + 2 = 4 fuel units `

Example 2:

Input: roads = [], seats = 1 Output: 0 Explanation: Only city 0 exists, the representative is already at the hub.

Example 3:

Input: roads = [[0,1],[0,2],[0,3]], seats = 5 Output: 3 Explanation: Each of cities 1, 2, and 3 sends one vehicle with their single representative directly to city 0. Total: 3 fuel units.