8634: Rock Tree

Professor Rockdu is interested in tree problems, and recently he has created a new data structure called Rock Tree.

Given a constant number k and a tree $T=V,E$ with $V$ as the node set and E as the edge set, a non-empty set of nodes A is called a Rock Tree of T if and only if

• $A\subseteq V$
• All nodes of A are connected in T which means for every pair of nodes u and v which are both in A, the nodes in the shortest path between u and v in T are all in A.
• The largest distance over every two nodes in A is not greater than k. The distance between two nodes u and v is defined as the number of nodes (including u and v) in the shortest path between u and v in the tree.

The first line contains a single integer T ($1\le T\le 100$), denoting the number of test cases.

For each test case, the first line contains two integers n,k (1≤n≤105, $1\le k\le n$), indicating the number of nodes and the distance limit.

The second line contains n integers a1,a2,…,an (∣ai∣≤104), indicating the value of nodes.

Each of the following n-1 lines contains two integers u,v ($1\le u,v\le n$), denoting an edge between u and v. It is guaranteed that these edges form a tree.

It is guaranteed that the sum of n over all test cases won't exceed 106, and there are at most 4 test cases with n>50000