A16786 | 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$ 时的答案。