g7-07684. 子树权值和 未做

给定一棵有 $n$ 个结点的树，结点编号为 $1$ 到 $n$，其中 $1$ 号结点是树根。每个结点 $i$ 有一个整数点权 $a_i$。

对于结点 $u$，它的子树由 $u$ 本身以及所有以 $u$ 为祖先的结点组成。请求出每个结点子树的点权之和（包含结点自身）。

第一行一个整数 $n$。

第二行 $n$ 个整数 $a_1,a_2,\dots ,a_n$，表示每个结点的点权。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示结点 $u$ 与结点 $v$ 之间有一条边。

数据保证给出的边构成一棵树。

输出一行 $n$ 个整数，第 $i$ 个整数表示结点 $i$ 的子树点权之和。

样例 1

输入：

5
1 2 3 4 5
1 2
1 3
2 4
2 5

输出：

15 11 3 4 5

解释：结点 $4$、$5$ 没有孩子，子树和分别为 $4$、$5$；结点 $2$ 的子树是 $\{2,4,5\}$，和为 $2+4+5=11$；结点 $3$ 的子树只有自己，和为 $3$；结点 $1$ 的子树是全部结点，和为 $1+2+3+4+5=15$。

样例 2

输入：

1
-7

输出：

-7

解释：只有一个结点，它的子树只包含自己，子树权值和就是它本身的点权。

• $1\le n\le 2\times 10^5$；
• $|a_i|\le 10^9$；
• 保证输入是一棵以 $1$ 号结点为根的树；
• 每个子树的权值和的绝对值不超过 $2\times 10^{14}$，可用 64 位整数存放。