给你一棵由 $$$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$$$ 中找到最大可能得分。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$ 整数。对于从 $$$1$$$ 到 $$$n$$$ 的每个 $$$x$$$,如果树以节点 $$$x$$$ 为根,则打印所有子集 $$$S$$$ 中的最大可能得分。
示例
输入复制
36 32 12 3 6 9 71 21 33 44 54 65 510000 1000 100 10 11 22 33 43 59 57 11 5 16 13 10 12 9 158 11 63 74 66 76 59 12 8
输出复制
27 57 30 39 51 4554311 15311 12511 12451 12415120 150 134 170 155 122 150 132 162
注意
在第一个测试用例中,树如下:
对于每个 $$$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\}$$$。