410299: GYM104003 G William and Spaceport

William is overseeing a system of spaceports in the galaxy of Glarble. Because space trips are expensive, spaceports generally try to have as few unnecessary flights as possible. In particular, the (two-way) flights can be represented by a tree, such that each planet in Glarble can be reached by each other planet in Glarble through some sequence of flights, but this sequence is unique (there is only one path from one planet to another).

Because different planets have different resources, each planet has an associated cost of visiting the planet. The cost of a trip from planet $$$u$$$ to planet $$$v$$$ ($$$u \neq v$$$), then, is the sum of the costs of all planets visited on the distinct path from $$$u$$$ to $$$v$$$. The total cost of the spaceport system is the sum of the costs of all distinct trips, where two trips are the same if they have the same starting planet and the same ending planet. Trips and flights begin and end on different planets.

William has the technological ability to upgrade spaceports; when he upgrades a spaceport, its cost decreases by one, unless the cost is already 0 in which case nothing happens. He can upgrade spaceports $$$K$$$ times (not necessarily distinct spaceports). He then wants to know: if he does this optimally, what's the minimum total cost of his new spaceport system?

The first line contains two integers $$$N$$$, $$$K$$$ ($$$1 \le N \le 10^5$$$, $$$1 \le K \le 10^9$$$), corresponding to the number of planets, and the number of upgrades William can perform, respectively.

The second line contains $$$N$$$ integers $$$c_1,...,c_N$$$ ($$$1 \le c_i \le 10^3$$$), where $$$c_i$$$ denotes the cost of visiting planet $$$i$$$.

The next $$$N-1$$$ lines contain two integers each, $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le N, u \neq v$$$), denoting that there is a two-way flight between planet $$$u$$$ and planet $$$v$$$.

Output a single integer, the minimum total cost of his new spaceport system if he upgrades spaceports optimally.

3 2
3 2 1
1 3
2 3

16

In the first example, we have 6 total trips, and the total cost of the spaceport system is 26. William can then upgrade spaceport 3 once and spaceport 1 once, and the new cost for the spaceport system is 16. It can be shown this is the least possible cost.