有一次,绮礼偷偷潜入了安兹贝伦家布满陷阱的庄园,却被基里图古的使魔发现了。评估了自己的实力后,绮礼决定撤退。该庄园被表示为一棵具有 $$$n$$$ 个顶点的树,其中 根 位于顶点 $$$1$$$。树的每个顶点都记录了一个数字$$$a_i$$$,代表了 危险 顶点 $$$i$$$ 的 。回想一下,树是一个没有循环的连通无向图。
为了成功撤退,绮礼必须计算 威胁 每个顶点的 值。的 顶点的 威胁 每个顶点的 等于 最大 交替 沿着从该顶点开始的垂直路径求和。的 交替 从顶点 $$$i$$$ 开始的垂直路径的总和定义为 $$$a_i - a_{p_i} + a_{p_{p_i}} - \ldots$$$,其中 $$$p_i$$$ 是到根(到顶点 $$$1$$$)的路径上顶点 $$$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$$$。
的 危险
顶点的 以红色表示。 帮助 Kirei 计算 威胁 每个顶点的 所有顶点的值并转义该属性。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
下面描述测试用例。
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 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 \cdot 10^5$$$。还保证给定的边集形成一棵树。
输出
对于每个测试用例,输出 $$$n$$$ 整数 - 每个顶点的 威胁 每个顶点的 。
示例
输入复制
254 5 2 6 71 23 24 35 161000000000 500500500 900900900 9 404 8008008003 45 12 51 66 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$$$。