CF2192D Cost of Tree

对于一棵以节点 $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$ 时的答案。

在第一个测试用例中，对于 $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$。 由 ChatGPT 5 翻译