Tap here to switch tabs
Problem
Submissions

Problem: Minimum Fuel Cost to Report to the Capital

Try to solve the Minimum Fuel Cost to Report to the Capital problem.

Statement

There is a tree consisting of nn cities numbered from 00 to n−1n - 1 and n−1n - 1 bidirectional roads, where roads[i] =[ai,bi]= [a_i, b_i] indicates a road connecting city aia_i and city bib_i. City 00 is the capital.

A representative from each city must travel to the capital to attend a meeting. There is initially one representative in each city.

Each car has an integer capacity of seats passengers. Driving a car between two directly connected cities consumes 11 liter of fuel. Representatives can travel together in the same car, change cars at any city, or park extra cars along the way to minimize the total fuel consumed.

Return the minimum total liters of fuel needed for all representatives to reach the capital.

Constraints:

  • 1≤n≤1051 \leq n \leq 10^5

  • roads.length =n−1= n - 1

  • roads[i].length =2= 2

  • 0≤ai,bi<n0 \leq a_i, b_i < n

  • ai≠bia_i \neq b_i

  • roads represents a valid tree.

  • 1≤1 \leq seats ≤105\leq 10^5

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Minimum Fuel Cost to Report to the Capital

Try to solve the Minimum Fuel Cost to Report to the Capital problem.

Statement

There is a tree consisting of nn cities numbered from 00 to n−1n - 1 and n−1n - 1 bidirectional roads, where roads[i] =[ai,bi]= [a_i, b_i] indicates a road connecting city aia_i and city bib_i. City 00 is the capital.

A representative from each city must travel to the capital to attend a meeting. There is initially one representative in each city.

Each car has an integer capacity of seats passengers. Driving a car between two directly connected cities consumes 11 liter of fuel. Representatives can travel together in the same car, change cars at any city, or park extra cars along the way to minimize the total fuel consumed.

Return the minimum total liters of fuel needed for all representatives to reach the capital.

Constraints:

  • 1≤n≤1051 \leq n \leq 10^5

  • roads.length =n−1= n - 1

  • roads[i].length =2= 2

  • 0≤ai,bi<n0 \leq a_i, b_i < n

  • ai≠bia_i \neq b_i

  • roads represents a valid tree.

  • 1≤1 \leq seats ≤105\leq 10^5