CF1901E Compressed Tree

给定一棵包含 $n$ 个顶点的树，每个顶点上写有一个数字，第 $i$ 个顶点上的数字为 $a_i$。 你可以进行如下操作任意次（可以为零次）： - 选择一个至多有 $1$ 条相邻边的顶点（即度数不超过 $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$ 表示，表示该边连接顶点 $v_i$ 和 $u_i$（$1 \le v_i, u_i \le n$，$v_i \ne u_i$）。这些边构成一棵树。 输入的额外限制：所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

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

由 ChatGPT 4.1 翻译