题目描述

给定一棵 $n$ 个点的树，第 $i$ 个点的权值为 $w_i$，并给定整数 $k$。

对于每个可能的根 $x$，需要选择一个大小为 $k$ 的点集 $S$，且必须满足 $x \in S$。

若 $f(i)$ 表示从点 $i$ 到根的路径上所有属于 $S$ 的点的权值和，请最大化：

对每个根 $x$ 输出对应的最大值。

输入格式

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

第一行包含整数 $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$），表示树上的一条边。

保证给出的图是一棵树，且所有测试数据的 $n$ 之和不超过 $4000$。

输出格式

对于每组测试数据，输出 $n$ 个整数。对每个 $x=1,2,\ldots,n$，输出以 $x$ 为根时所有合法集合 $S$ 的最大得分。

样例 1

3
6 3
2 12 3 6 9 7
1 2
1 3
3 4
4 5
4 6
5 5
10000 1000 100 10 1
1 2
2 3
3 4
3 5
9 5
7 11 5 16 13 10 12 9 15
8 1
1 6
3 7
4 6
6 7
6 5
9 1
2 8

27 57 30 39 51 45
54311 15311 12511 12451 12415
120 150 134 170 155 122 150 132 162

约束与提示

• 时间限制：2 秒

• 内存限制：1024 MB

• 原题编号：CF2229I