Carpooling to the Capital

Medium

A country has n cities numbered 0 to n − 1, joined by n − 1 two-way roads so that every city can reach every other (the roads form a tree). Road roads[i] = [a, b] connects cities a and b. City 0 is the capital. A convention is held in the capital, and every city sends one delegate there. Each city has one car with seats seats. A delegate can drive their own city's car or switch into another car along the way, as long as it has a free seat. Driving a car along one road costs 1 liter of fuel. Return the least amount of fuel needed to get every delegate to the capital.

Example 1

roads=[[0, 1], [1, 2], [1, 3]], seats=3 → 3

The delegates from cities 2 and 3 drive to city 1 in their own cars (2 liters). There all three get into one car and drive to the capital (1 liter). Total: 3.

Example 2

roads=[[0, 1], [1, 2], [2, 3]], seats=1 → 6

Each car has one seat, so everyone drives alone: 1 + 2 + 3 = 6 liters.

Example 3

roads=[], seats=4 → 0

Constraints

1 ≤ n ≤ 10⁵
len(roads) == n − 1
roads[i] = [a, b], 0 ≤ a, b < n, a ≠ b
The roads form a tree
1 ≤ seats ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Breadth-First Search Graph

Similar problems

Longest Hike Through the Woods Medium Links That Form a Single Tree Medium Rooms Open from the Hall Medium Treasure Gates Race Medium A Beetle Wandering a Tree Hard

Input

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

Expected

Run checks the first 3 tests in your browser. Submit checks all 68 tests on the server, hidden ones included.