A86022.LJJ 爱数树

NOI/NOI+/CTSC

通过率：0%

时间限制：1.00s

内存限制：256MB

题目描述

Eden 偶然间拿到了一张藏宝图，值得一提的是，这是张无向联通图，有 $n$ 个节点， $n-1$ 条长度为 $1$ 的边，我们称之为树。每个节点上都标有该地点的宝藏数量 $w_i$ 。

然而宝藏太多，不能一次性搬完，Eden 花费其所有积蓄买来 $k$ 个摄像头，每个摄像头能观测的距离范围是 $r$ （我们规定树上任意两点距离为其最短路径的长度）。为了确保宝藏尽可能不被他人拿走，Eden 将要在这棵树上的 $k$ 个节点处布置摄像头（于是与该节点距离小于等于 $r$ 的节点都能被观测到）。

Eden 想要使能被观测到的节点的宝藏数量（即 $w_i$ ）之和最大化，于是他把这个问题交给了爱数树的 LJJ，让 LJJ 枚举所有可能放置摄像头的情况，来筛选出最优的方案。

LJJ 数到一半，发现这个方案数量太多了，于是他把问题抛给了你，请你输出能被观测到的节点的 $w_i$ 之和的最大值。

为了使某乱搞算法不能通过，所以每组测试点有 $T$ 组数据。

输入格式

第一行，一个正整数 $T$ ，表示有 $T$ 组数据。

对于每组数据：
第一行：三个用空格分隔开的正整数 $n, k, r$ ；
第二行： $n$ 个用空格分隔开的正整数，第 $i$ 个数表示 $w_i$ ；
第三至第 $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\%$ 的数据， $1\le k\le n\le 20,0\lt r,w_i\le 20$ ；
对于 $40\%$ 的数据， $1\le k\le n\le 50,0\lt r,w_i\le 50$ ；
另有 $20\%$ 的数据， $k\le 2,n\le 1000,0\lt r\le 1000,0\lt w_i\le 10^6$ ；
另有 $10\%$ 的数据，给定的树是一条链；
对于全部数据， $1\le k\le n\le 1000,0\lt r\le 1000,0\lt w_i\le 10^6,1\le T\le 5,1\le x,y\le n$ 。

首页