CF2209F.Dynamic Values And Maximum Sum

You are given a tree$^{\text{∗}}$ with $n$ vertices numbered from 1 to $n$, where each vertex $i$ has an initial value $a_i$. You perform $k$ operations. The total is $0$ initially. In each operation:

1. Choose a vertex $r$ and root the tree at $r$.
2. Add the current value of $r$ to the total and set the value of $r$ to $0$.
3. For each vertex $ u $ that is not a leaf$^{\text{†}}$, find the leaves in the subtree$^{\text{‡}}$ of $u$ that are at the maximum distance from $u$. Among them, select the one with the smallest index, denoted as the destination for $u$. Add the current value of $u$ to the destination and set the value of $u$ to $0$.

Find the maximum possible total.

$^{\text{∗}}$A tree is a connected graph without cycles.

$^{\text{†}}$A leaf is any vertex without children.

$^{\text{‡}}$A subtree of vertex $v$ is the subgraph of $v$, all its descendants, and all the edges between them.

给你一棵有 $n$ 个顶点的树$^{\text{∗}}$，顶点编号为 $1$ 到 $n$，其中每个顶点 $i$ 有一个初始值 $a_i$。你需要执行 $k$ 次操作。初始时总和为 $0$。每次操作包含以下步骤：

1. 选择一个顶点 $r$，并将树以 $r$ 为根重新定向（即重设根节点）。
2. 将 $r$ 的当前值加到总和中，并将 $r$ 的值置为 $0$。
3. 对于每个非叶子顶点$^{\text{†}}$ $u$，找出其子树$^{\text{‡}}$ 中距离 $u$ 最远的所有叶子顶点；在这些叶子顶点中，选取编号最小者，记作 $u$ 的目标顶点。将 $u$ 的当前值加到该目标顶点上，并将 $u$ 的值置为 $0$。

求最终总和的最大可能值。

$^{\text{∗}}$ 树是无环的连通图。

$^{\text{†}}$ 叶子顶点指没有子节点的顶点。

$^{\text{‡}}$ 顶点 $v$ 的子树是指由 $v$、其所有后代顶点以及它们之间的所有边构成的子图。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10 ^ 4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($1 \le k \le n \le 3 \cdot 10^5$).

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the initial values of vertices.

Each of the following $n-1$ lines contains two integers $u$ and $v$, denoting an edge connecting vertex $u$ and $v$. It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $3\cdot 10 ^ 5$.

每个测试包含多个测试用例。第一行包含测试用例数量 $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$。

For each test case, output an integer — the maximum possible total.

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

In the first test case:

1. Choose vertex $1$ as the root. Add $a_1 = 19$ to the total and set $a_1 = 0$.

   After rooting the tree at $1$, for every non-leaf vertex $u$, move its value to the leaf in its subtree that is farthest from $u$ (breaking ties by smallest index). Under this rooting:

   • The value of vertex $2$ is transferred to vertex $4$, so $a_2$ becomes $0$ and $a_4$ becomes $101$.
   • The values of vertices $3$, $4$, and $5$ remain at their respective positions according to the rule.

2. Choose vertex $3$ as the root. Add $a_3 = 39$ to the total and set $a_3 = 0$.

   After redistribution under this rooting, the values of vertices $4$ and $5$ remain at their positions.

3. Choose vertex $4$ as the root. Add $a_4 = 101$ to the total and set $a_4 = 0$.

   After redistribution, the value at vertex $5$ remains unchanged.

4. Choose vertex $5$ as the root. Add $a_5 = 2$ to the total and set $a_5 = 0$.

The total obtained is $19 + 39 + 101 + 2 = 161$.

In the sixth test case, choose vertex $2$ as the root. Add its value to the total, obtaining $1\,000\,000\,000$.

在第一个测试用例中：

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$。