← 返回题目列表

Codeforces · 1901/E

E. 压缩树

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

给你一棵由 $$$n$$$ 个顶点组成的树。每个顶点上都写有一个数字;顶点 $$$i$$$ 上的数字等于 $$$a_i$$$。

您可以执行以下操作任意次数(可能为零):

- 选择一个最多具有 $$$1$$$ 关联边的顶点,并从树中删除该顶点。

请注意,您可以删除所有顶点。

完成所有操作后,您将压缩树。压缩过程如下完成。当树中存在恰好具有 $$$2$$$ 关联边的顶点时,请执行以下操作:

- 删除此顶点,用边连接其邻居。

可以看出,如果在压缩过程中有多种方式选择要删除的顶点,则生成的树仍然是相同的。

你的任务是在应用上述操作任意次后计算顶点上写入的最大可能数字总和,然后压缩树。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$) — 顶点数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$)。

接下来的 $$$n - 1$$$ 行描述了树的一条边。边 $$$i$$$ 由两个整数 $$$v_i$$$ 和 $$$u_i$$$ 表示,即它连接的顶点的标签($$$1 \le v_i, u_i \le n$$$, $$$v_i \ne u_i$$$)。这些边形成一棵树。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 在应用上述操作任意次然后压缩树后在顶点上写入的最大可能数字总和。

示例

输入 #1

3
4
1 -2 2 1
1 2
3 2
2 4
2
-2 -5
2 1
7
-2 4 -2 3 3 2 -1
1 2
2 3
3 4
3 5
4 6
4 7

输出 #1

3
0
9