← 返回题目列表

Codeforces · 2192/D

D. 树的成本

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

对于具有根 $$$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$$$ 的边。可以看出,经过此操作,图仍然是一棵树。
作为示例,下面显示了 $$$r=1$$$、$$$u=5$$$ 和 $$$v=4$$$ 的操作示例。

$$$^{\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$$$ 的答案。

示例

输入
复制

3
5
1 3 2 1 2
1 2
2 3
3 4
3 5
7
1 2 3 1 3 2 1
1 2
2 3
3 4
4 5
4 6
3 7
5
5 4 3 2 1
1 2
2 3
3 4
4 5

输出
复制

18 10 5 0 0
40 28 18 8 0 0 0
20 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$$$。