H. 野树的曙
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

小曙有一棵包含 $$$n$$$ 个节点的无根树 $$$T$$$，节点编号为 $$$1, 2, \dots, n$$$。同时，他手中有一个包含 $$$n$$$ 个正整数的多重集 $$$S = \{s_1, s_2, \dots, s_n\}$$$。

小曙需要为树上的每个节点 $$$u$$$ 分配一个来自集合 $$$S$$$ 的点权 $$$w_u$$$，使得集合 $$$S$$$ 中的每个元素恰好分配给一个节点。

对于树上的任意一对有序节点 $$$(x, y)$$$，定义其路径权值 $$$f(x, y)$$$ 为节点 $$$x$$$ 到节点 $$$y$$$ 的简单路径上所有节点的点权之和（包含端点 $$$x$$$ 和 $$$y$$$）。

请你帮小曙确定一种点权分配方案，使得整棵树的总路径权值之和最大，即最大化：$$$$$$\sum_{u=1}^n \sum_{v=1}^n f(u, v)$$$$$$

Input

第一行输入一个正整数 $$$T\ (1\le T\le 10^4)$$$，表示测试组数。

接下来的 $$$T$$$ 组测试中，输入格式如下：

  • 第一行输入一个正整数 $$$n\ (2\le n\le 2\times 10^5)$$$，表示节点个数。
  • 第二行输入 $$$n$$$ 个正整数 $$$s_1,s_2,\dots,s_n\ (1\le s_i\le 10^9)$$$，表示多重集 $$$S$$$。
  • 接下来 $$$n-1$$$ 行，每行共输入两个正整数 $$$x,y\ (1\le x,y\le n,x\neq y)$$$，表示一条树边，数据保证给出的树边一定是一棵树。

此外，数据保证所有测试点 $$$n$$$ 的总和不超过 $$$2\times 10^5$$$。

Output

对于每组测试，共输出一行：

  • 共输出 $$$n$$$ 个正整数，第 $$$i$$$ 个正整数表示节点 $$$i$$$ 的点权 $$$w_i$$$。

如果存在多种合法解，输出任意一种合法方案即可通过本题。

Example
Input
4
3
2 1 4
1 2
2 3
4
5 7 8 1
1 2
2 3
3 4
8
10 5 6 15 9 12 33 10
1 2
2 5
4 5
5 3
8 7
3 7
3 6
10
1 2 3 4 5 6 7 8 9 10
1 2
2 4
4 9
8 3
8 7
5 4
2 8
6 8
6 10
Output
2 4 1
5 8 7 1
10 12 33 9 15 6 10 5
6 9 5 8 4 7 3 10 2 1
Note

对于样例二：

一种最优的点权分配方案：$$$w_1 = 1, w_2 = 8, w_3 = 7, w_4 = 5$$$。

计算部分代表性有序点对的简单路径权值：

  • $$$f(1, 1) = 1, \quad f(2, 2) = 8, \quad f(3, 3) = 7, \quad f(4, 4) = 5$$$
  • $$$f(1, 2) = f(2, 1) = 1 + 8 = 9$$$
  • $$$f(2, 3) = f(3, 2) = 8 + 7 = 15$$$
  • $$$f(1, 4) = f(4, 1) = 1 + 8 + 7 + 5 = 21$$$
将所有 $$$4 \times 4 = 16$$$ 个有序点对的路径权值 $$$f(u, v)$$$ 全部累加，可得总权值和的最大值为 $$$207$$$。