LJJ 爱数树
题目描述
Eden 偶然间拿到了一张藏宝图,值得一提的是,这是张无向联通图,有 $n$ 个节点,$n-1$ 条长度为 $1$ 的边,即一颗树。每个节点上都标有该地点的宝藏数量 $w_i$。
然而宝藏太多,不能一次性搬完,Eden 花费其所有积蓄买来 $k$ 个摄像头,每个摄像头能观测的距离范围是 $r$(我们规定树上任意两点距离为其最短路径的长度)。为了确保宝藏尽可能不被他人拿走,Eden 将要在这棵树上的至多 $k$ 个节点处布置摄像头(于是与该节点距离 $\le r$ 的节点都能被观测到)。
Eden 想要使能被观测到的节点的宝藏数量(即 $w_i$)之和最大化,于是他把这个问题交给了爱数树的 LJJ。让 LJJ 枚举所有可能放置摄像头的情况,来筛选出最优的方案。
LJJ 数到一半,发现这个方案数量太多了,于是他把问题抛给了你,
请你输出能被观测到的节点的 $w_i$ 之和的最大值。
输入输出格式
输入格式
**本题有多组数据。**
第 $1$ 行:一个正整数 $T$,表示有 $T$ 组数据。
接下来每组数据:\
第 $1$ 行:$3$ 个用空格分隔开的正整数 $n, k, r$。\
第 $2$ 行:$n$ 个用空格分隔开的正整数,第 $i$ 个数表示 $w_i$。\
第 $3$ 至 $n+1$ 行:每行两个整数 $x,y$,表示 $x$ 到 $y$ 之间有一条边。
输出格式
对于每组数据,一行输出一个整数,表示能被观测到的节点的 $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\%$ 的数据,保证 $n\le20$,$r\le 20$,$w_i\le20$;
对于 $40\%$ 的数据,保证 $n\le50$,$r\le 50$,$w_i\le50$;
对于另外 $20\%$ 的数据,保证 $k\le2$;
对于另外 $10\%$ 的数据,保证给出的树是一条链。
对于 $100\%$ 的数据,保证 $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$。
官方题解请查看 [https://www.cnblogs.com/Blog-of-Eden/p/9367521.html](https://www.cnblogs.com/Blog-of-Eden/p/9367521.html)。