CF2229I The Endians

给定一棵有 $n$ 个节点的树，其中第 $i$ 个节点的权值为 $w_i$，以及一个整数 $k$。 假设以节点 $x$ 作为根节点。你可以选择一个大小为 $k$ 的节点子集 $S$，且 $x \in S$。设 $f(i)$ 为从节点 $i$ 到根节点的路径上，所有属于 $S$ 的节点权值的和。集合 $S$ 的分数为 $\sum_{i \in S} f(i)$。 对于每个 $1 \le x \le n$，你需要求出以节点 $x$ 作为根节点时，所有满足条件的子集 $S$ 中分数的最大值。

每个测试点包含多组测试数据。第一行包含一个整数 $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$。

对于每组测试数据，输出 $n$ 个整数。对于每个 $x$ 从 $1$ 到 $n$，输出以 $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\}$。 由 ChatGPT 5 翻译