Problem Description

Eden accidentally obtained a treasure map. Notably, it is an undirected connected graph with $n$ nodes and $n-1$ edges of length $1$, i.e., a tree. Each node is labeled with the amount of treasure at that location, $w_i$.

However, there is too much treasure to move all at once. Eden spent all his savings to buy $k$ cameras. Each camera has an observation range of $r$ (we define the distance between any two points on the tree as the length of their shortest path). To ensure that the treasure is not taken by others as much as possible, Eden will place cameras at at most $k$ nodes on the tree (so all nodes whose distance to that node is $\le r$ can be observed).

Eden wants to maximize the sum of treasure amounts (i.e., $w_i$) of the nodes that can be observed, so he gave this problem to LJJ, who loves counting trees. He asked LJJ to enumerate all possible camera placements to find the best plan.

Halfway through counting, LJJ realized there were far too many plans, so he threw the problem to you. Please output the maximum possible sum of $w_i$ over the nodes that can be observed.

Input Format

This problem contains multiple test cases.

Line $1$: a positive integer $T$, indicating there are $T$ test cases.

For each test case:
Line $1$: three positive integers $n, k, r$ separated by spaces.
Line $2$: $n$ positive integers separated by spaces; the $i$-th number denotes $w_i$.
Lines $3$ to $n+1$: each line 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, indicating the maximum possible sum of $w_i$ of the nodes that can be observed.

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

10
18

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

34
46
61

Hint

For $10\%$ of the testdata, it is guaranteed that $n\le20$, $r\le 20$, $w_i\le20$.

For $40\%$ of the testdata, it is guaranteed that $n\le50$, $r\le 50$, $w_i\le50$.

For another $20\%$ of the testdata, it is guaranteed that $k\le2$.

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

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

For the official editorial, please see https://www.cnblogs.com/Blog-of-Eden/p/9367521.html.

Translated by ChatGPT 5