题目描述

星图馆保存着一份由 $n$ 个观测站组成的树形星图。第 $i$ 个观测站有一个能量值 $w_i$。

现在需要为每一个观测站 $x$ 分别建立一份归档。建立以 $x$ 为核心的归档时，整棵树会被看作以 $x$ 为根的有根树。

你需要选择一个大小恰好为 $k$ 的观测站集合 $S$，并且必须满足 $x\in S$。对于任意 $i\in S$，定义 $f(i)$ 为从 $i$ 到根 $x$ 的路径上，所有属于 $S$ 的观测站的能量值之和。

这份归档的评分为：

对于每一个 $1\le x\le n$，请你求出以 $x$ 为根时，所有合法集合 $S$ 中评分的最大值。

输入格式

每个测试点包含多组测试数据。

第一行包含一个整数 $T$，表示测试数据组数。

对于每组测试数据：

第一行包含两个整数 $n,k$。

第二行包含 $n$ 个整数 $w_1,w_2,\ldots,w_n$。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示观测站 $u$ 和 $v$ 之间有一条通道。

保证每组数据给出的图是一棵树。

输出格式

对于每组测试数据，输出一行 $n$ 个整数。第 $x$ 个整数表示以 $x$ 为根时的最大评分。

样例 1 输入

1
6 3
2 12 3 6 9 7
1 2
1 3
3 4
4 5
4 6

样例 1 输出

27 57 30 39 51 45

样例 2 输入

1
5 5
10000 1000 100 10 1
1 2
2 3
3 4
3 5

样例 2 输出

54311 15311 12511 12451 12415

样例 3

见选手目录下的 tree/tree3.in 与 tree/tree3.ans。

该样例满足子任务 $1$ 的约束条件。

样例 4

见选手目录下的 tree/tree4.in 与 tree/tree4.ans。

该样例满足子任务 $2$ 的约束条件。

样例 5

见选手目录下的 tree/tree5.in 与 tree/tree5.ans。

该样例满足子任务 $3$ 的约束条件。

样例 6

见选手目录下的 tree/tree6.in 与 tree/tree6.ans。

该样例满足子任务 $4$ 的约束条件。

样例 7

见选手目录下的 tree/tree7.in 与 tree/tree7.ans。

该样例满足子任务 $5$ 的约束条件。

数据范围

对于所有测试数据，均满足：

• $1\le T\le 500$；
• $2\le n\le 4000$；
• $1\le k\le n$；
• $1\le w_i\le 10^9$；
• 每个输入文件中所有测试数据的 $n$ 之和不超过 $4000$。

本题采用捆绑测试。每个子任务内的测试点必须全部通过，才能获得该子任务分数。