← 返回题目列表

Codeforces · 2229/I

I. 字节序

中文机器翻译题面 查看原题

给你一棵由 $$$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$$$ 中的最大可能得分。

示例

输入
复制

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

注意

在第一个测试用例中,树如下:

对于每个 $$$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\}$$$。