All problems

Best Depot Town

Hard · tree dp

A region has n towns, numbered 0 to n - 1, joined by n - 1 two-way roads. Each entry of roads is [a, b, length]: a road between towns a and b that is length kilometres long. The roads are laid out so that you can drive from any town to any other, and there is exactly one way to do it without driving back over a road. The list homes gives the number of households in each town (homes[i] for town i).

A delivery company will build one depot in one of the towns. Every household is served by one trip from the depot to its town, and a trip costs as many units as the kilometres driven along the roads. So the total cost of a depot in town t is the sum, over all towns v, of homes[v] times the distance from t to v. Households in the depot's own town cost nothing.

Return [t, cost]: the town with the smallest total cost and that cost. If several towns have the same smallest cost, return the one with the lowest number.

Examples

Example 1

Input: homes = [2, 1, 3], roads = [[0, 1, 4], [1, 2, 1]]

Output: [1, 11]

Town 0 costs 1 * 4 + 3 * 5 = 19. Town 1 costs 2 * 4 + 3 * 1 = 11. Town 2 also costs 2 * 5 + 1 * 1 = 11, but town 1 has the lower number.

Example 2

Input: homes = [0, 3, 3, 3], roads = [[0, 1, 2], [0, 2, 2], [0, 3, 2]]

Output: [0, 18]

Town 0 is the hub: each of the three outer towns is 2 km away, so the cost is 3 * 2 * 3 = 18. Any outer town costs more.

Constraints