Minimum Fuel Cost to Report to the Capital

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:

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:

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:

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