CF1901E.Compressed Tree

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.

给你一棵包含 $n$ 个顶点的树。每个顶点上写有一个数字；顶点 $i$ 上的数字为 $a_i$。

你可以执行以下操作任意多次（包括零次）：

• 选择一个至多只与一条边相连的顶点，并将该顶点从树中删除。

注意：你可以删除所有顶点。

在完成所有上述操作后，你需要对剩余的树进行压缩。压缩过程如下：只要树中存在恰好与两条边相连的顶点，就重复执行以下操作：

• 删除该顶点，并将其两个邻居用一条边直接连接。

可以证明：在压缩过程中，若存在多种可选的顶点进行删除，最终得到的树仍唯一。

你的任务是：通过任意次数地执行上述删除操作，再对结果树进行压缩，求出最终树中所有顶点上的数字之和的最大可能值。

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

第一行包含一个整数 $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$。

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.

对于每个测试用例，输出一个整数——在任意次数地执行上述操作后，再对树进行压缩，顶点上数字之和所能达到的最大值。