시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
3 초 256 MB 78 37 34 45.946%

문제

연약한 사람들이 모여 사는 나라가 있다. 이 곳에는 N 개의 도시들이 있고, 두 도시 사이를 연결하는 길이 N − 1개 있어 어느 두 도시도 오직 하나의 경로로만 서로 통행할 수 있게 되어 있다.

이 곳에는 몇 년에 한 번씩 전염병이 창궐하여 큰 피해가 일어난다. 정부에서는 이 문제를 해결하기 위해 N −1 개의 길들 중 K 개의 길에 검역소를 운영하려고 한다. 검역소는 감염된 사람이 지나가지 못하게 함으로서 전염병이 전파될 수 없는 장벽과 같은 역할을 해 준다.

하지만 검역소들만으로는 전염병이 일어나지 못하게 할 수는 없다. 따라서 어떤 사람이 전염병에 감염될 경우를 대비하여 치료제를 비축해 두려고 한다. 어떤 한 사람이 전염병에 감염될 때에도 전염병에 걸릴 수 있는 모든 사람들이 치료제를 하나씩 받을 수 있게 하기 위해 비축해야 할 치료제의 최소 개수를 구하여라.

입력

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

각 테스트 케이스의 첫 번째 줄에는 도시의 개수를 의미하는 자연수 N(2 ≤ N ≤ 100, 000)과 설치할 수 있는 검역소의 개수 K(1 ≤ KN − 1)가 주어진다.

두 번째 줄에는 N 개의 자연수가 주어지며, i번째 자연수는 i번 도시의 인구 Xi(1 ≤ Xi ≤ 1, 000, 000, 000)를 의미한다.

세 번째 줄부터 N − 1개의 줄에는 도로의 정보가 한 줄에 하나씩 주어진다. 한 줄에는 두 개의 정수 Ai , Bi (1 ≤ Ai ≤ N, 1 ≤ Bi ≤ N)가 주어지며 이것은 Ai 번 도시와 Bi 번 도시가 도로로 연결되어 있음을 의미한다.

출력

전염병이 퍼질 경우에 대비해 정부에서 비축해야 하는 치료제의 개수를 하나의 정수로 출력한다.

예제 입력

1
5 2
3 9 7 2 5
1 3
2 4
3 5
4 3

예제 출력

11

힌트

3번 도시와 5번 도시를 잇는 도로와 4번 도시와 3번 도시를 잇는 도로에 검역소를 설치하면 치료제를 11 인분만 비축해도 된다. 1번 도시에 전염병이 발생할 경우 1번 도시와 3번 도시의 10명의 사람들이, 2번 도시에 전염병이 발생할 경우 2번 도시와 4번 도시의 11명의 사람들이, 3번 도시에 발생할 경우 10명, 4 번 도시에 발생할 경우 11명, 5번 도시에 발생할 경우 5명이 감염될 수 있으므로 어느 경우에도 11인분의 치료제로 충분히 전염병을 막을 수 있다.