A16869. Dynamic Values And Maximum Sum

给定一棵有 $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. 选择顶点 $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$。以 $3$ 为根时，$4$ 和 $5$ 上的值仍保留原位置。
3. 选择顶点 $4$ 作为根。将 $a_4=101$ 加入总和，并置 $a_4=0$。以 $4$ 为根时，$5$ 上的值仍保留原位置。
4. 选择顶点 $5$ 作为根。将 $a_5=2$ 加入总和，并置 $a_5=0$。

最终总和为 $19+39+101+2=161$。

在第六个测试用例中，选择顶点 $2$ 作为根，则总和为 $1 \, 000 \, 000 \, 000$。