问题描述
Byteland有$n$个城市和$n-1$条道路, 他们构成了一棵树. 城市标号从$1$到$n$, 第$i$个城市人口是$p_i$.
Byteland的国王Soda, 想要沿着最短路从某个城市$u$旅游到另一个城市$v$. 如果经过的城市的最大人口和最小人口之差小于等于$D$, Soda会很开心. 于是Soda想要知道有多少对不同的$(u,v)$会使得他开心.
输入描述
输入有多组数据. 第一行有一个整数$T$ $(1 \le T \le 100)$, 表示测试数据组数. 然后对于每组数据:
第一行有两个整数$n$和$D$ $(1 \le n \le 100000, 1 \le D \le 10^9)$.
第二行包含$n$个整数 $p_1, p_2, \dots, p_n$ $(0 \le p_i \le 10^9)$, 表示每个城市的人口.
接下来$n-1$行, 每行包含两个整数$u$和$v$ $(1 \le u, v \le n, u \ne v)$, 表示城市$u$和城市$v$之间有一条道路相连.
保证所有数据中$n$的和不超过$5 \times 10^5$.
输出描述
对于每组数据, 输出能是Soda开心的$(u,v)$数目.
输入样例
1
3 3
1 2 3
1 2
2 3
输出样例
6
Hint
If you need a larger stack size,
please use #pragma comment(linker, "/STACK:102400000,102400000") and submit your solution using C++.
