검역소

연약한 사람들이 모여 사는 나라가 있다. 이 나라에는 도시가 $N$개 있고 두 도시를 잇는 길이 $N-1$개 있어서, 어느 두 도시 사이에도 이동 경로가 정확히 하나씩 존재한다.

이 나라에는 몇 년에 한 번씩 전염병이 크게 번져 큰 피해를 남긴다. 정부는 이 문제를 해결하려고 $N-1$개의 길 가운데 $K$개를 골라 그 길에 검역소를 세우려고 한다. 검역소가 세워진 길은 감염된 사람이 지나갈 수 없어서 전염병을 막는 장벽이 된다.

검역소만으로 전염병을 없앨 수는 없다. 그래서 정부는 치료제를 미리 비축해 두려고 한다. 어느 도시의 어떤 사람이 처음 감염되더라도, 그 유행으로 감염될 수 있는 모든 사람이 치료제를 하나씩 받을 수 있어야 한다. 검역소 $K$개를 가장 잘 배치했을 때 비축해야 하는 치료제의 최소 개수를 구하여라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 도시의 개수 $N$($2 \le N \le 100000$)과 세울 수 있는 검역소의 개수 $K$($1 \le K \le N-1$)가 주어진다.

둘째 줄에는 자연수 $N$개가 주어진다. $i$번째 수 $X_i$($1 \le X_i \le 1000000000$)는 $i$번 도시의 인구다.

셋째 줄부터 $N-1$개의 줄에 길의 정보가 한 줄에 하나씩 주어진다. 각 줄에는 두 정수 $A_i$, $B_i$($1 \le A_i \le N$, $1 \le B_i \le N$)가 주어지며, $A_i$번 도시와 $B_i$번 도시가 길로 이어져 있다는 뜻이다.

각 테스트 케이스마다 비축해야 하는 치료제의 최소 개수를 한 줄에 하나씩 출력한다.

첫 번째 예제에서 3번 도시와 5번 도시를 잇는 길, 4번 도시와 3번 도시를 잇는 길에 검역소를 세우면 치료제 11인분으로 충분하다. 1번 도시에서 전염병이 시작되면 1번과 3번 도시의 10명이, 2번 도시에서 시작되면 2번과 4번 도시의 11명이, 3번 도시에서 시작되면 10명이, 4번 도시에서 시작되면 11명이, 5번 도시에서 시작되면 5명이 감염될 수 있다. 어느 경우에도 11인분이면 모자라지 않는다.