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]之和的最大值

输入输出样例

输入样例 #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

输出样例 #1

10
18

输入样例 #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

输出样例 #2

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