← 返回题目

题库练习 Dynamic Values And Maximum Sum

← 上一题下一题 →

A16869 | $Dynamic Values And Maximum Sum$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定一棵有 $n$ 个顶点的树 $^{\text{∗}}$，顶点编号为 $1$ 到 $n$，每个顶点 $i$ 有一个初始值 $a_i$。你可以执行 $k$ 次操作，总和初始为 $0$。每次操作如下： 1. 选择一个顶点 $r$，并将树的根定为 $r$。 2. 将当前 $r$ 的值加到总和中，并将 $r$ 的值设为 $0$。 3. 对于每个不是叶子的顶点 $u$，在 $u$ 的子树 $^{\text{‡}}$ 中，找到距离 $u$ 最远的叶子 $^{\text{†}}$；若有多个，则选择编号最小的那个，记为 $u$ 的目的地。将 $u$ 当前的值加到目的地的值上，并将 $u$ 的值设为 $0$。 请你求出可能得到的最大总和。 $^{\text{∗}}$ 树是无环连通图。 $^{\text{†}}$ 叶子是没有子节点的顶点。 $^{\text{‡}}$ 顶点 $v$ 的子树是 $v$、其所有后代以及它们之间所有边所构成的子图。

输入格式

每个测试包含多个测试用例。第一行包含测试用例数 $t$ （$1 \le t \le 10 ^ 4$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含两个整数 $n$ 和 $k$ （$1 \le k \le n \le 3 \cdot 10^5$）。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1\le a_i \le 10^9$），表示各顶点的初始值。 随后的 $n-1$ 行，每行包含两个整数 $u, v$，表示 $u$ 和 $v$ 之间有一条边。保证这些边构成一棵树。 保证所有测试用例中 $n$ 的总和不超过 $3\cdot 10 ^ 5$。

输出格式

对于每个测试用例，输出一个整数，表示可能得到的最大总和。

输入输出样例

输入 #1

7
5 4
19 20 39 81 2
1 2
1 3
2 4
2 5
5 3
12 21 39 8 21
1 2
1 3
3 4
2 5
5 2
129 216 32 83 221
1 2
1 3
3 4
4 5
5 3
15 15 15 15 15
1 2
1 3
1 4
1 5
1 1
1
2 1
1 1000000000
1 2
7 2
8 3 5 7 9 1 6
4 3
7 5
5 2
2 3
3 6
6 1

输出 #1

C++ 编辑器

输入

输出