Problem Description

Eden偶然间拿到了一张藏宝图，值得一提的是，这是张无向联通图，有$n$个节点，$n-1$条长度为$1$的边，即一颗树。每个节点上都标有该地点的宝藏数量$w_i$。

然而宝藏太多，不能一次性搬完，Eden花费其所有积蓄买来$k$个摄像头，每个摄像头能观测的距离范围是$r$（我们规定树上任意两点距离为其最短路径的长度）。为了确保宝藏尽可能不被他人拿走，Eden将要在这棵树上的至多$k$个节点处布置摄像头（于是与该节点距离$\le r$的节点都能被观测到）。

Eden想要使能被观测到的节点的宝藏数量（即$w_i$）之和最大化，于是他把这个问题交给了爱数树的LJJ。让LJJ枚举所有可能放置摄像头的情况，来筛选出最优的方案。

LJJ数到一半，发现这个方案数量太多了，于是他把问题抛给了你，请你输出能被观测到的节点的$w_i$之和的最大值。

Input Format

This problem contains multiple test cases.

The first line: a positive integer $T$, indicating there are $T$ test cases.

For each test case:
- The first line: three positive integers $n, k, r$ separated by spaces.
- The second line: $n$ positive integers separated by spaces, where the $i$-th number represents $w_i$.
- The third to the $n+1$-th lines: each contains two integers $x, y$, indicating there is an edge between $x$ and $y$.

Output Format

For each test case, output one integer per line, representing the maximum sum of $w_i$ of the nodes that can be observed.

Sample Input and Output

Sample Input #1

2
9 1 1
2 2 2 2 2 3 4 3 4
1 2
1 3
1 4
1 5
2 6
6 7
3 8
8 9
9 2 1
2 2 2 2 2 3 4 3 4
1 2
1 3
1 4
1 5
2 6
6 7
3 8
8 9

Sample Output #1

10
18

Sample Input #2

3
10 1 1
2 8 9 6 1 9 9 2 8 9 
1 2
2 3
2 4
4 5
3 6
2 7
7 8
4 9
7 10
10 2 1
2 8 9 6 1 9 9 2 8 9 
1 2
2 3
2 4
4 5
3 6
2 7
7 8
4 9
7 10
10 3 1
2 8 9 6 1 9 9 2 8 9 
1 2
2 3
2 4
4 5
3 6
2 7
7 8
4 9
7 10

Sample Output #2

34
46
61

Notes/Hints

For $10\%$ of the data, it is guaranteed that $n \le 20$, $r \le 20$, $w_i \le 20$;

For $40\%$ of the data, it is guaranteed that $n \le 50$, $r \le 50$, $w_i \le 50$;

For another $20\%$ of the data, it is guaranteed that $k \le 2$;

For another $10\%$ of the data, it is guaranteed that the given tree is a chain.

For $100\%$ of the data, it is guaranteed that $1 \le k \le n \le 10^3$, $1 \le r \le 10^3$, $1 \le w_i \le 10^6$, $1 \le T \le 5$, $1 \le x, y \le n$.

For the official solution, please refer to https://www.cnblogs.com/Blog-of-Eden/p/9367521.html.

见题面 Input 部分

见题面 Output 部分