410299: GYM104003 G William and Spaceport

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. William and Spaceporttime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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?

Input

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

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

ExampleInput
3 2
3 2 1
1 3
2 3
Output
16
Note

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.

加入题单

算法标签: