这个问题用的深搜还是回溯算法比较好?一个C语言算法的选择,请教大家

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

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!