CF2114E.Kirei Attacks the Estate

有一次，Kirei 偷偷潜入了 Ainzbern 家族布满陷阱的庄园，但被 Kiritugu 的使魔发现了。评估了自己的实力后，Kirei 决定撤退。庄园被表示为一棵有 $n$ 个结点的树，根节点为结点 $1$。树上每个结点 $i$ 都有一个数字 $a_i$，表示结点 $i$ 的危险值。树是一个无环连通无向图。

为了顺利撤退，Kirei 需要计算每个结点的威胁值。一个结点的威胁值定义为：从该结点出发沿着向根的路径，所有“交错和”的最大值。结点 $i$ 的“交错和”定义为 $a_i - a_{p_i} + a_{p_{p_i}} - \ldots$，其中 $p_i$ 表示 $i$ 的父节点（到根节点 $1$ 的路径上）。

例如，在下图的树中，结点 $4$ 有如下几条向根的路径：

• $[4]$，交错和为 $a_4 = 6$；
• $[4, 3]$，交错和为 $a_4 - a_3 = 6 - 2 = 4$；
• $[4, 3, 2]$，交错和为 $6 - 2 + 5 = 9$；
• $[4, 3, 2, 1]$，交错和为 $6 - 2 + 5 - 4 = 5$。

结点的危险值用红色标出。请帮助 Kirei 计算所有结点的威胁值，并顺利逃离庄园。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。

接下来描述每个测试用例。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 2 \times 10^5$），表示树的结点数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le 10^9$），表示每个结点的危险值。

接下来的 $n-1$ 行，每行包含两个整数 $v, u$（$1 \le v, u \le n$，$v \neq u$），表示树中的一条边。

保证所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。保证给定的边集构成一棵树。

对于每个测试用例，输出 $n$ 个整数，依次表示每个结点的威胁值。

第一个测试用例的树如题面所示，各结点的最大交错和如下：

1. $a_1 = 4$；
2. $a_2 = 5$；
3. $a_3 = 2$；
4. $a_4 - a_3 + a_2 = 6 - 2 + 5 = 9$；
5. $a_5 = 7$。

由 ChatGPT 4.1 翻译