← 返回题目列表

Codeforces · 2209/F

F. 动态值和最大总和

中文机器翻译题面 查看原题

给你一棵树$$$^{\text{*}}$$$,其中 $$$n$$$ 顶点编号从 1 到 $$$n$$$,其中每个顶点 $$$i$$$ 都有一个初始值 $$$a_i$$$。您执行 $$$k$$$ 操作。最初总计为 $$$0$$$。在每个操作中:

  1. 选择一个顶点 $$$r$$$ 并将树根设在 $$$r$$$ 处。
  2. 将 $$$r$$$ 的当前值添加到总计中,并将 $$$r$$$ 的值设置为 $$$0$$$。
  3. 对于不是叶子 $$$^{\text{†}}$$$ 的每个顶点 $$$u$$$,查找 $$$u$$$ 的子树 $$$^{\text{‡}}$$$ 中与 $$$u$$$ 距离最大的叶子。其中,选择索引最小的一个,表示为$$$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$$$。

输出

对于每个测试用例,输出一个整数 - 最大可能总数。

示例

输入
复制

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

输出
复制

161
101
681
60
1
1000000000
32

注意

在第一个测试用例中:

  1. 选择顶点 $$$1$$$ 作为根。将 $$$a_1 = 19$$$ 添加到总数中并设置 $$$a_1 = 0$$$。

    在 $$$1$$$ 为树定根后,对于每个非叶顶点 $$$u$$$,将其值移动到其子树中距离 $$$u$$$ 最远的叶(通过最小索引打破联系)。在此生根下:

    • 顶点$$$2$$$的值被转移到顶点$$$4$$$,因此$$$a_2$$$变为$$$0$$$,$$$a_4$$$变为$$$101$$$。
    • 顶点 $$$3$$$、$$$4$$$ 和 $$$5$$$ 的值根据规则保持在各自的位置。

  2. 选择顶点 $$$3$$$ 作为根。将 $$$a_3 = 39$$$ 添加到总数中并设置 $$$a_3 = 0$$$。

    在此根下重新分配后,顶点 $$$4$$$ 和 $$$5$$$ 的值保持在其位置。

  3. 选择顶点 $$$4$$$ 作为根。将 $$$a_4 = 101$$$ 添加到总数中,并设置 $$$a_4 = 0$$$。

    重新分配后,顶点 $$$5$$$ 处的值保持不变。

  4. 选择顶点 $$$5$$$ 作为根。将 $$$a_5 = 2$$$ 添加到总数中并设置 $$$a_5 = 0$$$。

获得的总金额为 $$$19 + 39 + 101 + 2 = 161$$$。

在第六个测试用例中,选择顶点 $$$2$$$ 作为根。将其值添加到总数中,得到 $$$1\,000\,000\,000$$$。