CF2192D.Cost of Tree

For a tree $T$ with root $r$, where each node $u$ has a value $a_u$ associated with it, the cost of the tree defined as:

$$\\sum\_{u\\in T} (a\_u \\cdot d(r,u))$$

Here, this sum is taken over all nodes $u$ in the tree $T$, and $d(r,u)$ denotes the number of edges on the shortest path from node $r$ to node $u$ on a tree.

You are given a tree consisting of $n$ nodes, rooted at node $1$. Each node $i$ has a value $a_i$ assigned to it. For each $r$ from $1$ to $n$, please solve the following problem independently:

Consider the subtree of node $r$ with respect to node $1$. Formally, the subtree of node $r$ is the tree consisting of all nodes $u$ such that the shortest path from $1$ to $u$ contains $r$.

Find the maximum cost of the subtree after performing at most one operation of the following type on the subtree:

• Choose any node $u$ ($u \neq r$). Remove the edge from $u$ to the parent of node $u$$^{\text{∗}}$. Then, add an edge from $u$ to any node $v$ that is still reachable from $r$. It can be shown that after this operation, the graph remains a tree.

As an example, below shows an example of an operation with $r=1$,$u=5$, and $v=4$.

$^{\text{∗}}$Formally, remove the edge from $u$ to $p$, where $p$ is the unique node satisfying $d(u,p)=1$ and $d(u,r)=d(p,r)+1$

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

考虑以节点 $1$ 为参考时节点 $r$ 的子树。形式化地，节点 $r$ 的子树是指所有满足“从节点 $1$ 到节点 $u$ 的最短路径经过 $r$”的节点 $u$ 所构成的树。

在对该子树至多执行一次如下操作的前提下，求该子树所能达到的最大代价：

• 任选一个节点 $u$（要求 $u \neq r$）。删除节点 $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$ 的节点。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each testcase contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the count of nodes in the tree.

The second line of each testcase contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 2 \cdot 10^5$).

Then $n − 1$ lines follow, the $i$-th line containing two integers $u$ and $v$ ($1 \le u, v \le n$) — the two nodes that the $i$-th edge connects.

It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ over all test cases.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, print $n$ numbers – the answers for $r=1,2,\ldots,n$.

对于每个测试用例，输出 $n$ 个数字——即 $r=1,2,\ldots,n$ 对应的答案。

In the first test case, for $r=1$, it is optimal to choose $u=5$ and $v=4$. The cost of the tree is then $1\cdot 0 + 3\cdot 1+2\cdot 2+1\cdot 3+2\cdot 4=18$. It can be shown that a larger cost cannot be obtained over all legal operations.

For $r=4$ for example, there is only $1$ node in the subtree, so there is no operation possible. The only possible cost of the subtree is $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$。