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