CF2229I.The Endians

You are given a tree of $n$ nodes, where node $i$ has weight $w_i$, and an integer $k$.

Let the tree be rooted at node $x$. You may select a subset $S$ of the nodes such that $|S| = k$ and $x \in S$. Let $f(i)$ be the sum of the weights of all nodes in $S$ on the path from node $i$ to the root. The score of $S$ is $\sum_{i \in S} f(i)$.

For each node $1 \le x \le n$, find the maximum possible score among all subsets $S$ if the tree is rooted at node $x$.

给你一棵包含 $n$ 个节点的树，其中节点 $i$ 的权值为 $w_i$，以及一个整数 $k$。

将树以节点 $x$ 为根。你可以选择一个节点子集 $S$，满足 $|S| = k$ 且 $x \in S$。令 $f(i)$ 表示从节点 $i$ 到根节点的路径上所有属于 $S$ 的节点的权值之和。子集 $S$ 的得分为 $\sum_{i \in S} f(i)$。

对每个节点 $1 \le x \le n$，求当树以节点 $x$ 为根时，所有满足条件的子集 $S$ 所能获得的最大得分。

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

The first line of each test case contains two integers $n$ and $k$ ($2 \le n \le 4000$, $1 \le k \le n$).

The second line of each test case contains $n$ integers $w_1, w_2,\ldots, w_n$ ($1 \le w_i \le 10^9$).

Each of the next $n - 1$ lines contains two integers $u$ and $v$ ($1 \le u, v \le n$), indicating that nodes $u$ and $v$ are connected by an edge. It is guaranteed that the given graph is a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed $4000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 500$）。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 4000$，$1 \le k \le n$）。

每个测试用例的第二行包含 $n$ 个整数 $w_1, w_2,\ldots, w_n$（$1 \le w_i \le 10^9$）。

接下来的 $n - 1$ 行中，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$），表示节点 $u$ 和 $v$ 之间存在一条边。保证所给图是一棵树。

保证所有测试用例的 $n$ 值之和不超过 $4000$。

For each test case, print $n$ integers. For each $x$ from $1$ to $n$, print the maximum possible score among all subsets $S$ if the tree is rooted at node $x$.

对于每个测试用例，输出 $n$ 个整数。对于每个从 $1$ 到 $n$ 的 $x$，输出当树以节点 $x$ 为根时，所有子集 $S$ 所能获得的最大可能得分。

In the first test case, the tree is as follows:

For each $1 \le x \le n$, the following is an optimal set $S$:

• $x = 1$: $S = {1, 2, 5}$; the score is $(2) + (12 + 2) + (9 + 2) = 27$,
• $x = 2$: $S = {2, 4 ,5}$; the score is $(12) + (6 + 12) + (9 + 6 + 12) = 57$,
• $x = 3$: $S = {2, 3, 5}$; the score is $(12 + 3) + (3) + (9 + 3) = 30$,
• $x = 4$: $S = {2, 4, 5}$; the score is $(12 + 6) + (6) + (9 + 6) = 39$,
• $x = 5$: $S = {2, 4 ,5}$; the score is $(12 + 6 + 9) + (6 + 9) + (9) = 51$,
• $x = 6$: $S = {2 ,4, 6}$; the score is $(12 + 6 + 7) + (6 + 7) + (7) = 45$.

In the second test case, $S = {1, 2, 3, 4, 5}$ for all $x$.

在第一个测试用例中，树的结构如下：

对每个 $1 \le x \le n$，以下为一个最优集合 $S$：

• $x = 1$：$S = \{1, 2, 5\}$；得分为 $(2) + (12 + 2) + (9 + 2) = 27$，
• $x = 2$：$S = \{2, 4, 5\}$；得分为 $(12) + (6 + 12) + (9 + 6 + 12) = 57$，
• $x = 3$：$S = \{2, 3, 5\}$；得分为 $(12 + 3) + (3) + (9 + 3) = 30$，
• $x = 4$：$S = \{2, 4, 5\}$；得分为 $(12 + 6) + (6) + (9 + 6) = 39$，
• $x = 5$：$S = \{2, 4, 5\}$；得分为 $(12 + 6 + 9) + (6 + 9) + (9) = 51$，
• $x = 6$：$S = \{2, 4, 6\}$；得分为 $(12 + 6 + 7) + (6 + 7) + (7) = 45$。

在第二个测试用例中，对所有 $x$，均有 $S = \{1, 2, 3, 4, 5\}$。