CF1466D.13th Labour of Heracles

You've probably heard about the twelve labors of Heracles, but do you have any idea about the thirteenth? It is commonly assumed it took him a dozen years to complete the twelve feats, so on average, a year to accomplish every one of them. As time flows faster these days, you have minutes rather than months to solve this task. But will you manage?

In this problem, you are given a tree with $n$ weighted vertices. A tree is a connected graph with $n - 1$ edges.

Let us define its $k$-coloring as an assignment of $k$ colors to the edges so that each edge has exactly one color assigned to it. Note that you don't have to use all $k$ colors.

A subgraph of color $x$ consists of these edges from the original tree, which are assigned color $x$, and only those vertices that are adjacent to at least one such edge. So there are no vertices of degree $0$ in such a subgraph.

The value of a connected component is the sum of weights of its vertices. Let us define the value of a subgraph as a maximum of values of its connected components. We will assume that the value of an empty subgraph equals $0$.

There is also a value of a $k$-coloring, which equals the sum of values of subgraphs of all $k$ colors. Given a tree, for each $k$ from $1$ to $n - 1$ calculate the maximal value of a $k$-coloring.

你可能听说过赫拉克勒斯的十二项功绩，但你知道第十三项吗？人们普遍认为他花了十二年才完成这十二项壮举，因此平均下来，每项壮举耗时一年。而如今时间流逝得更快了，你只有几分钟（而非数月）来解决本题。你能否成功？

本题中，你将得到一棵含 $n$ 个带权顶点的树。树是一种具有 $n - 1$ 条边的连通图。

我们定义该树的一个 $k$-染色（$k$-coloring）为：将 $k$ 种颜色之一分配给每条边，使得每条边恰好被赋予一种颜色。（注意：你不必使用全部 $k$ 种颜色。）

颜色为 $x$ 的子图由原树中所有被染成颜色 $x$ 的边，以及仅包含至少与一条此类边相邻的顶点所构成。因此，该子图中不存在度为 $0$ 的顶点。

一个连通分量的值定义为该连通分量中所有顶点的权值之和。我们定义一个子图的值为它的所有连通分量的值中的最大值。我们约定：空子图的值为 $0$。

此外，一个 $k$-染色的值定义为所有 $k$ 种颜色对应的子图的值之和。给定一棵树，请对每个 $k = 1, 2, \dots, n - 1$，计算其 $k$-染色所能达到的最大值。

In the first line of input, there is a single integer $t$ ($1 \leq t \leq 10^5$) denoting the number of test cases. Then $t$ test cases follow.

First line of each test case contains a single integer $n$ ($2 \leq n \leq 10^5$). The second line consists of $n$ integers $w_1, w_2, \dots, w_n$ ($0 \leq w_i \leq 10^9$), $w_i$ equals the weight of $i$-th vertex. In each of the following $n - 1$ lines, there are two integers $u$, $v$ ($1 \leq u,v \leq n$) describing an edge between vertices $u$ and $v$. It is guaranteed that these edges form a tree.

The sum of $n$ in all test cases will not exceed $2 \cdot 10^5$.

输入的第一行包含一个整数 $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$。

For every test case, your program should print one line containing $n - 1$ integers separated with a single space. The $i$-th number in a line should be the maximal value of a $i$-coloring of the tree.

对于每个测试用例，你的程序应输出一行，包含 $n - 1$ 个整数，整数之间用单个空格分隔。该行中第 $i$ 个数应为该树的一个 $i$-着色的最大值。

The optimal $k$-colorings from the first test case are the following:

In the $1$-coloring all edges are given the same color. The subgraph of color $1$ contains all the edges and vertices from the original graph. Hence, its value equals $3 + 5 + 4 + 6 = 18$.

In an optimal $2$-coloring edges $(2, 1)$ and $(3,1)$ are assigned color $1$. Edge $(4, 3)$ is of color $2$. Hence the subgraph of color $1$ consists of a single connected component (vertices $1, 2, 3$) and its value equals $3 + 5 + 4 = 12$. The subgraph of color $2$ contains two vertices and one edge. Its value equals $4 + 6 = 10$.

In an optimal $3$-coloring all edges are assigned distinct colors. Hence subgraphs of each color consist of a single edge. They values are as follows: $3 + 4 = 7$, $4 + 6 = 10$, $3 + 5 = 8$.

第一个测试用例的最优 $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$。