310864: CF1901E. Compressed Tree

E. Compressed Treetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a tree consisting of $n$ vertices. A number is written on each vertex; the number on vertex $i$ is equal to $a_i$.

You can perform the following operation any number of times (possibly zero):

• choose a vertex which has at most $1$ incident edge and remove this vertex from the tree.

Note that you can delete all vertices.

After all operations are done, you're compressing the tree. The compression process is done as follows. While there is a vertex having exactly $2$ incident edges in the tree, perform the following operation:

• delete this vertex, connect its neighbors with an edge.

It can be shown that if there are multiple ways to choose a vertex to delete during the compression process, the resulting tree is still the same.

Your task is to calculate the maximum possible sum of numbers written on vertices after applying the aforementioned operation any number of times, and then compressing the tree.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 5 \cdot 10^5$) — the number of vertices.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^9 \le a_i \le 10^9$).

Each of the next $n - 1$ lines describes an edge of the tree. Edge $i$ is denoted by two integers $v_i$ and $u_i$, the labels of vertices it connects ($1 \le v_i, u_i \le n$, $v_i \ne u_i$). These edges form a tree.

Additional constraint on the input: the sum of $n$ over all test cases doesn't exceed $5 \cdot 10^5$.

Output

For each test case, print a single integer — the maximum possible sum of numbers written on vertices after applying the aforementioned operation any number of times, and then compressing the tree.

ExampleInput

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

Output

3
0
9

题目大意：
你有一棵包含n个顶点的树，每个顶点都有一个数字a_i。你可以进行任意次数（可能为零）的以下操作：选择一个最多只有一个相邻边的顶点，并从树中移除这个顶点。在所有操作完成后，你将树进行压缩。压缩过程是：当树中存在恰好有两个相邻边的顶点时，删除这个顶点，并将其邻居连接起来。如果压缩过程中有多个选择顶点的方案，最终得到的树是相同的。你的任务是计算在执行任意次数的操作并压缩树后，顶点上数字的最大可能和。

输入数据格式：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
每个测试用例的第一行包含一个整数n（2≤n≤5×10^5）——顶点的数量。
第二行包含n个整数a_1, a_2, ..., a_n（-10^9≤a_i≤10^9）。
接下来的n-1行描述了树的一条边。边i由两个整数v_i和u_i表示，它们是边连接的顶点标签（1≤v_i, u_i≤n，v_i≠u_i）。这些边构成了一棵树。
输入数据的附加限制：所有测试用例的n之和不超过5×10^5。

输出数据格式：
对于每个测试用例，打印一个整数——在执行上述操作任意次数并压缩树后，顶点上数字的最大可能和。题目大意： 你有一棵包含n个顶点的树，每个顶点都有一个数字a_i。你可以进行任意次数（可能为零）的以下操作：选择一个最多只有一个相邻边的顶点，并从树中移除这个顶点。在所有操作完成后，你将树进行压缩。压缩过程是：当树中存在恰好有两个相邻边的顶点时，删除这个顶点，并将其邻居连接起来。如果压缩过程中有多个选择顶点的方案，最终得到的树是相同的。你的任务是计算在执行任意次数的操作并压缩树后，顶点上数字的最大可能和。 输入数据格式： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 每个测试用例的第一行包含一个整数n（2≤n≤5×10^5）——顶点的数量。 第二行包含n个整数a_1, a_2, ..., a_n（-10^9≤a_i≤10^9）。 接下来的n-1行描述了树的一条边。边i由两个整数v_i和u_i表示，它们是边连接的顶点标签（1≤v_i, u_i≤n，v_i≠u_i）。这些边构成了一棵树。 输入数据的附加限制：所有测试用例的n之和不超过5×10^5。 输出数据格式： 对于每个测试用例，打印一个整数——在执行上述操作任意次数并压缩树后，顶点上数字的最大可能和。