LJJ爱数树

题解请查看[https://www.cnblogs.com/Blog-of-Eden/p/9367521.html](https://www.cnblogs.com/Blog-of-Eden/p/9367521.html)

Eden偶然间拿到了一张藏宝图，值得一提的是，这是张**无向联通图**，有**n个节点**，**n-1条长度为1的边**，我们称之为**树**。每个节点上都标有该地点的宝藏数量**w[i]**。 然而宝藏太多，不能一次性搬完，Eden花费其所有积蓄买来**k**个摄像头，每个摄像头能观测的**距离范围是r（我们规定树上任意两点距离为其最短路径的长度）**。为了确保宝藏尽可能不被他人拿走，Eden将要在这棵树上的k个节点处布置摄像头（于是与该节点距离<=r的节点都能被观测到）。 Eden想要**使能被观测到的节点的宝藏数量(w[i])之和最大化**，于是他把这个问题交给了爱数树的LJJ。能够确定的是**k<=n<=1000，0<r<=1000，0<w[i]<=1e6**。 让LJJ枚举所有可能放置摄像头的情况，来筛选出最优的方案。 LJJ数到一半，发现这个方案数量太多了，于是他把问题抛给了你， 请你输出**能被观测到的节点的w[i]之和的最大值**。 为了使某乱搞算法不能通过，所以每组测试点**有T组数据**。**T<=5**

第一行：一个正整数 T (T<=5)，表示有T组数据 接下来每组数据： 第1行：3个用空格分隔开的正整数n, k, r 第2行：n个用空格分隔开的正整数，第i个数表示w[i] 第3至n+1行：每行两个整数1<=x,y<=n，表示x到y之间有一条边

对于每组数据一行输出一个整数：sum，表示能被观测到的节点的w[i]之和的最大值

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

10%：1<=k<=n<=20，0<r<=20，0<w[i]<=20 40%：1<=k<=n<=50，0<r<=50，0<w[i]<=50 另外有20%数据：k<=2，n<=1000，0<r<=1000，0<w[i]<=1e6 另外有10%数据：给定的树是一条链 100%：1<=k<=n<=1000，0<r<=1000，0<w[i]<=1e6