E. Kirei 突袭庄园
每个测试点时间限制：$2$ 秒
内存限制：$256$ 兆字节

---

题目描述

某天，Kirei 潜入了 Ainzbern 家族布满陷阱的庄园，却被 Kiritugu 的使魔发现。评估了自己的实力后，Kirei 决定撤退。

庄园可以表示为一棵有 $n$ 个节点的树，根节点为 $1$。每个节点 $i$ 上有一个数字 $a_i$，表示该节点的危险程度。

为了成功撤退，Kirei 需要计算每个节点的威胁值。一个节点的威胁值定义为：从该节点出发，沿着到根节点的路径（即向上走到节点 $1$）的所有垂直路径中，交替和的最大值。

垂直路径：从节点 $i$ 出发，沿着父节点方向向上走若干步（可以不走）形成的节点序列。

交替和的定义为：
$a_i - a_{p_i} + a_{p_{p_i}} - \dots$ 其中 $p_i$ 表示节点 $i$ 的父节点，依此类推直到根节点（符号交替：第一个节点取正，第二个取负，第三个取正，……）。

---

示例

在下图所示的树中，节点 $4$ 的所有垂直路径及其交替和如下：

• $[4]$：$a_4 = 6$
• $[4,3]$：$a_4 - a_3 = 6 - 2 = 4$
• $[4,3,2]$：$a_4 - a_3 + a_2 = 6 - 2 + 5 = 9$
• $[4,3,2,1]$：$a_4 - a_3 + a_2 - a_1 = 6 - 2 + 5 - 4 = 5$

所以节点 $4$ 的威胁值为 $\max(6,4,9,5) = 9$。

节点中的红色数字表示 $a_i$。

请帮助 Kirei 计算所有节点的威胁值，让他安全逃离庄园。

---

输入格式

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

每个测试用例：

• 第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）—— 树的节点数。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$）—— 节点的危险值。
• 接下来 $n-1$ 行，每行包含两个整数 $v, u$（$1 \le v, u \le n, v \ne u$）—— 树的一条边。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$，且给定的边构成一棵树。

---

输出格式

对于每个测试用例，输出 $n$ 个整数 —— 每个节点的威胁值。

---

输入样例

2
5
4 5 2 6 7
1 2
3 2
4 3
5 1
6
1000000000 500500500 900900900 9 404 800800800
3 4
5 1
2 5
1 6
6 4

输出样例

4 5 2 9 7 
1000000000 1500500096 1701701691 199199209 404 800800800 

---

样例解释

第一个测试用例的树结构与题目描述中的图一致：

• $a_1 = 4$
• $a_2 = 5$
• $a_3 = 2$
• $a_4 - a_3 + a_2 = 6 - 2 + 5 = 9$
• $a_5 = 7$