Quarantine Stations

There is a country where frail people live. It has $N$ cities and $N-1$ roads, each road joining two cities, and between any two cities there is exactly one route.

Every few years an epidemic spreads through the country and does heavy damage. To hold it back, the government picks $K$ of the $N-1$ roads and builds a quarantine station on each of them. An infected person cannot pass a road that has a quarantine station, so such a road becomes a barrier against the epidemic.

Quarantine stations alone cannot end the epidemic, so the government also stockpiles doses of a cure. Whoever is infected first, and in whichever city, every person who can catch the disease in that outbreak must receive one dose. Find the smallest stockpile that suffices when the $K$ quarantine stations are placed in the best possible way.

The first line contains the number of test cases $T$.

The first line of each test case contains the number of cities $N$ ($2 \le N \le 100000$) and the number of quarantine stations $K$ ($1 \le K \le N-1$).

The second line contains $N$ positive integers. The $i$-th of them, $X_i$ ($1 \le X_i \le 1000000000$), is the population of city $i$.

Each of the next $N-1$ lines contains two integers $A_i$ and $B_i$ ($1 \le A_i \le N$, $1 \le B_i \le N$), meaning that city $A_i$ and city $B_i$ are joined by a road.

For each test case, print the smallest number of doses to stockpile on its own line.

In the first example, build quarantine stations on the road between city 3 and city 5 and on the road between city 4 and city 3. Then 11 doses are enough. An outbreak that starts in city 1 can infect the 10 people of cities 1 and 3, one that starts in city 2 can infect the 11 people of cities 2 and 4, one that starts in city 3 can infect 10 people, one that starts in city 4 can infect 11 people, and one that starts in city 5 can infect 5 people. In every case 11 doses cover everyone.