CFCF2192D.Cost of Tree

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

对于一棵以节点 $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$ 。对于每个 $r$ （ $r$ 从 $1$ 到 $n$ ），请独立地解决如下问题：

考虑以节点 $1$ 为根时，关于节点 $r$ 的“子树”——即包含所有满足从 $1$ 到 $u$ 的最短路径经过 $r$ 的节点 $u$ 的那棵树。对于这个子树：

在最多进行一次如下操作后，求子树的最大代价：

任选一个节点 $u$ （ $u\neq r$ ）。删除节点 $u$ 与其父节点之间的边 $^*$ 。然后，将 $u$ 与仍然能从 $r$ 到达的任意节点 $v$ 相连。可以证明，执行该操作后，图依然保持为树。

如下图，是 $r=1$ ， $u=5$ ， $v=4$ 时的一次操作示例。

$^*$ 更正式地说，是删除 $u$ 到 $p$ 的边，其中 $p$ 是唯一满足 $d(u,p)=1$ 且 $d(u,r)=d(p,r)+1$ 的节点。

每个测试用例包含多组数据。第一行包含一个整数 $t$ （ $1\leq t\leq 10^4$ ）——表示测试用例的组数。

每组测试用例的第一行包含一个整数 $n$ （ $1 \leq n \leq 2 \times 10^5$ ）——树的节点数。

接下来一行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ （ $1 \leq a_i \leq 2 \times 10^5$ ）。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$ （ $1\leq u, v\leq n$ ），表示第 $i$ 条边连接的两个节点。

保证所给的边形成一棵树。

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

对于每组测试用例，输出 $n$ 个数——依次为 $r=1,2,\ldots,n$ 时的答案。

输入#1

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

输出#1

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$ ，只有一个节点在该子树中，不存在可进行的操作。此时子树的唯一代价为 $0$ 。