U650090 pre 的树题1

pre 爱树！ PRE 杯（#2026.1.14 Lv.2）T4（CF1500）。

给定一棵有 $n$ 个节点的树，节点编号 1 到 $n$ 每个节点 $i$ 有一个权值 $a_i$. 你可以进行以下操作任意次（包括零次）： 1.选择树中的一条边 $(u,v)$。 2.删除这条边，得到两棵子树。 3.选择其中一棵子树，将它所有节点的权值都乘以 $-1$。 操作结束后，计算整棵树（注意操作后它可能不连通）所有节点权值的和。经过若干次操作后，这个和最大可能是多少？给出这个值。

第一行为 $t$。 每组第一行为 $n$，第二行为 $a_i$，后 $n - 1$ 行为 $(u,v)$。

$t$ 行，每行为题意中的最大值。

对于 $100\%$ 的数据，$1 \le n \le 5 \times 10 ^ 5,1 \le \sum n \le 5 \times 10 ^ 5,-10 \le a_i \le 10$。 你的所有测试点的输出全部正确，你将得到 $100$ 分，反之 $0$ 分。