U646530 pre 的树题2

pre 爱树！ PRE 杯（#2026.1.14 Lv.2）T5（CF1600）。

给定一棵包含 $n$ 个顶点的无根树，节点编号 $1$ 到 $n$，每个节点 $i$ 有一个权值 $a_i$。求对于每个顶点 $v$,在所有包含顶点 $v$ 的连通块 $E$ 中，$\sum a_i (i \in E)$ 最大值是多少？多组数据。

第一行为 $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,-100 \le a_i \le 100$。 你的所有测试点的输出全部正确，你将得到 $100$ 分，反之 $0$ 分。