← 返回题目列表

Codeforces · 1466/D

D. 赫拉克勒斯第十三功

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

你可能听说过赫拉克勒斯的十二项功绩,但是你知道第十三项功绩吗?人们普遍认为他花了十几年的时间来完成这十二项壮举,因此平均来说,完成每一项壮举都需要一年的时间。如今时间过得越来越快,您只需几分钟而不是几个月的时间来解决此任务。但你能做到吗?

在此问题中,您将获得一棵具有 $$$n$$$ 加权顶点的树。树是一个具有 $$$n - 1$$$ 边的连通图。

让我们将其 $$$k$$$ 着色定义为将 $$$k$$$ 颜色分配给边缘,以便每个边缘都分配有一种颜色。请注意,您不必使用所有 $$$k$$$ 颜色。

颜色 $$$x$$$ 的子图由原始树中的这些边组成,这些边被分配颜色 $$$x$$$,并且仅包含与至少一个这样的边相邻的那些顶点。所以在这样的子图中不存在度为 $$$0$$$ 的顶点。

连接组件的值是其顶点权重的总和。让我们将子图的值定义为其连接分量的最大值。我们假设空子图的值等于$$$0$$$。

还有一个 $$$k$$$ 颜色的值,它等于所有 $$$k$$$ 颜色的子图值的总和。给定一棵树,对于从 $$$1$$$ 到 $$$n - 1$$$ 的每个 $$$k$$$ 计算 $$$k$$$ 着色的最大值。

输入

在输入的第一行中,有一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) 表示测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 10^5$$$)。第二行由 $$$n$$$ 整数 $$$w_1, w_2, \dots, w_n$$$ ($$$0 \leq w_i \leq 10^9$$$) 组成,$$$w_i$$$ 等于第 $$$i$$$ 个顶点的权重。在以下 $$$n - 1$$$ 行中,有两个整数 $$$u$$$、$$$v$$$ ($$$1 \leq u,v \leq n$$$) 描述顶点 $$$u$$$ 和 $$$v$$$ 之间的边。保证这些边形成一棵树。

所有测试用例中$$$n$$$的总和不会超过$$$2 \cdot 10^5$$$。

输出

对于每个测试用例,您的程序应打印一行,其中包含 $$$n - 1$$$ 整数,并用一个空格分隔。一行中的第 $$$i$$$ 数字应该是树的 $$$i$$$ 着色的最大值。

示例

输入 #1

4
4
3 5 4 6
2 1
3 1
4 3
2
21 32
2 1
6
20 13 17 13 13 11
2 1
3 1
4 1
5 1
6 1
4
10 6 6 6
1 2
2 3
4 1

输出 #1

18 22 25
53
87 107 127 147 167
28 38 44

注意

第一个测试用例的最佳 $$$k$$$ 着色如下:

在$$$1$$$着色中,所有边缘都被赋予相同的颜色。颜色 $$$1$$$ 的子图包含原始图中的所有边和顶点。因此,其价值等于 $$$3 + 5 + 4 + 6 = 18$$$。

在最佳 $$$2$$$ 着色中,$$$(2, 1)$$$ 和 $$$(3,1)$$$ 被分配颜色 $$$1$$$。边 $$$(4, 3)$$$ 的颜色为 $$$2$$$。因此,颜色 $$$1$$$ 的子图由单个连通分量(顶点 $$$1, 2, 3$$$)组成,其值等于 $$$3 + 5 + 4 = 12$$$。颜色 $$$2$$$ 的子图包含两个顶点和一条边。它的价值等于$$$4 + 6 = 10$$$。

在最佳 $$$3$$$ 着色中,所有边缘都被分配不同的颜色。因此,每种颜色的子图都由一条边组成。它们的值如下:$$$3 + 4 = 7$$$、$$$4 + 6 = 10$$$、$$$3 + 5 = 8$$$。