Happy King

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 $p_i$.

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.

There are multiple test cases. The first line of input contains an integer $T$ $(1 \le T \le 500)$, indicating the number of test cases. For each test case:

The first line contains two integers $n$ and $D$ $(1 \le n \le 100000, 1 \le D \le 10^9)$.

The second line contains $n$ integers $p_1, p_2, \dots, p_n$ $(0 \le p_i \le 10^9)$.

Each of the following $n - 1$ lines describing roads contains two integers $u, v$ $(1 \le u, v \le n, u \ne 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 \times 10^5$.

For each test case, output the number of different pairs that can make Soda happy.

1
3 3
1 2 3
1 2
2 3

6

If you need a larger stack size,
please use #pragma comment(linker, "/STACK:102400000,102400000") and submit your solution using C++.

BestCoder 1st Anniversary ($)