对于具有根 $$$r$$$ 的树 $$$T$$$,其中每个节点 $$$u$$$ 都有一个与其关联的值 $$$a_u$$$,树的成本定义为:
$$\sum_{u\in T} (a_u \cdot d(r,u))$$
这里,这个总和是对树 $$$T$$$ 中的所有节点 $$$u$$$ 求和,$$$d(r,u)$$$ 表示树上从节点 $$$r$$$ 到节点 $$$u$$$ 的最短路径上的边数。
给你一棵由 $$$n$$$ 节点组成的树,根节点为 $$$1$$$。每个节点 $$$i$$$ 都有一个分配给它的值 $$$a_i$$$。对于从$$$1$$$到$$$n$$$的每一个$$$r$$$,请独立解决以下问题:
考虑节点 $$$r$$$ 相对于节点 $$$1$$$ 的子树。形式上,节点$$$r$$$的子树是由所有节点$$$u$$$组成的树,使得从$$$1$$$到$$$u$$$的最短路径包含$$$r$$$。
执行后求子树的最大成本 最多 1 个 在子树上进行以下类型的操作:
- 选择任意节点 $$$u$$$ ($$$u \neq r$$$)。删除从 $$$u$$$ 到节点 $$$u$$$$$$^{\text{*}}$$$ 的父节点的边。然后,添加一条从 $$$u$$$ 到仍可从 $$$r$$$ 到达的任何节点 $$$v$$$ 的边。可以看出,经过此操作,图仍然是一棵树。
$$$^{\text{*}}$$$正式地,删除从 $$$u$$$ 到 $$$p$$$ 的边,其中 $$$p$$$ 是满足 $$$d(u,p)=1$$$ 和 $$$d(u,r)=d(p,r)+1$$$ 的唯一节点
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 树中的节点数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$)。
然后是 $$$n − 1$$$ 行,第 $$$i$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$) — 第 $$$i$$$ 条边连接的两个节点。
保证给定的边形成一棵树。
保证所有测试用例中 $$$n$$$ 的总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印 $$$n$$$ 数字 - $$$r=1,2,\ldots,n$$$ 的答案。
示例
输入复制
351 3 2 1 21 22 33 43 571 2 3 1 3 2 11 22 33 44 54 63 755 4 3 2 11 22 33 44 5
输出复制
18 10 5 0 040 28 18 8 0 0 020 10 4 1 0
注意
在第一个测试用例中,对于 $$$r=1$$$,最佳选择为 $$$u=5$$$ 和 $$$v=4$$$。那么树的成本是$$$1\cdot 0 + 3\cdot 1+2\cdot 2+1\cdot 3+2\cdot 4=18$$$。可见,不可能获得比所有合法操作都更大的成本。
例如,对于$$$r=4$$$,子树中只有$$$1$$$节点,因此无法进行操作。子树唯一可能的成本是$$$0$$$。