← 返回题目列表

Codeforces · 2114/E

E. Kirei 袭击庄园

中文机器翻译题面 查看原题

有一次,绮礼偷偷潜入了安兹贝伦家布满陷阱的庄园,却被基里图古的使魔发现了。评估了自己的实力后,绮礼决定撤退。该庄园被表示为一棵具有 $$$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$$$ 整数 - 每个顶点的 威胁 每个顶点的 。

示例

输入
复制

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 

注意

语句中描述了第一个测试用例的树,并且最大 变量符号 总和如下:

  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$$$。