Problem Description
There are n cities and n−1 roads in Byteland, and they form a tree. The cities are numbered 1 through n. The population in i-th city is pi.
Soda, the king of Byteland, wants to travel from a city u to another city v along the shortest path. Soda would be happy if the difference between the maximum and minimum population among the cities passed is no larger than D. So, your task is to tell Soda how many different pairs (u,v) that can make him happy.
Input
There are multiple test cases. The first line of input contains an integer T (1≤T≤500), indicating the number of test cases. For each test case:
The first line contains two integers n and D (1≤n≤100000,1≤D≤109).
The second line contains n integers p1,p2,…,pn (0≤pi≤109).
Each of the following n−1 lines describing roads contains two integers u,v (1≤u,v≤n,u≠v) meaning that there is a road connecting city u and city v.
It is guaranteed that the total number of vertices in the input doesn't exceed 5×105.
Output
For each test case, output the number of different pairs that can make Soda happy.
Sample Input
1
3 3
1 2 3
1 2
2 3
Sample Output
6
