A91496.最大颜色子树

给定一棵包含 $n$ 个顶点的树。树是一个包含 $n-1$ 条边的连通无向图。树上的每个顶点 $v$ 都被赋予了一种颜色（如果顶点 $v$ 是白色，则 $a_v = 1$，如果顶点 $v$ 是黑色，则 $a_v = 0$）。

你需要对于每个顶点 $v$，解决如下问题：在所有包含顶点 $v$ 的子树中，白色顶点数与黑色顶点数的最大差值是多少？
树的子树是原树的一个连通子图。更正式地说，如果你选择的子树包含 $cnt_w$ 个白色顶点和 $cnt_b$ 个黑色顶点，你需要最大化 $cnt_w - cnt_b$。

第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示树的顶点数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 1$），其中 $a_i$ 表示第 $i$ 个顶点的颜色。

接下来 $n-1$ 行，每行描述一条树的边。第 $i$ 条边由两个整数 $u_i$ 和 $v_i$ 表示，表示该边连接顶点 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n, u_i \ne v_i$）。

保证给定的边构成一棵树。

输出 $n$ 个整数 $res_1, res_2, \dots, res_n$，其中 $res_i$ 表示在所有包含顶点 $i$ 的子树中，白色顶点数与黑色顶点数的最大差值。

样例解释

样例 #1

颜色：白点记为 +1，黑点记为 −1：

• 1:−1, 2:+1, 3:+1, 4:+1, 5:−1, 6:−1, 7:−1, 8:−1, 9:+1

对每个点，找一棵「包含该点的连通子树」，使得这些点的权值和最大：

• 点 1：例如选子树 {1,2,3,4}，和 = −1+1+1+1 = 2，不能更大，所以 res₁ = 2；
• 点 3：例如选 {3,4}，和 = 1+1 = 2，所以 res₃ = 2；
• 点 5：例如选 {3,4,5,9}，和 = 1+1−1+1 = 2，所以 res₅ = 2；
• 点 6：例如选 {1,2,3,4,6}，和 = −1+1+1+1−1 = 1，所以 res₆ = 1；
• 点 8：最多选到和 = 0（如 {1,2,3,4,6,8}），所以 res₈ = 0。

其余点也可类似枚举，最终得到输出：

2 2 2 2 2 1 1 0 2。

---

样例 #2

颜色转权值：

• 1:−1, 2:−1, 3:+1, 4:−1

• 点 3：选 {3}，和 = 1，为最大，res₃ = 1；

• 点 2：选 {2}，和 = −1，比包含 1 的任何更大子树都好，res₂ = −1；

• 点 4：同理，res₄ = −1；

• 点 1：选 {1,3}，和 = −1+1 = 0，为最大，res₁ = 0。

所以输出为：

0 -1 1 -1。