题目描述

给定一棵包含 $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$ 的子树中，白色顶点数与黑色顶点数的最大差值。

9
0 1 1 1 0 0 0 0 1
1 2
1 3
3 4
3 5
2 6
4 7
6 8
5 9

2 2 2 2 2 1 1 0 2

4
0 0 1 0
1 2
1 3
1 4

0 -1 1 -1

说明/提示

第一个样例如下图所示：

黑色顶点用粗边框表示。

在第二个样例中，顶点 $2, 3, 4$ 的最优子树分别是顶点 $2, 3, 4$ 本身。顶点 $1$ 的最优子树是包含顶点 $1$ 和 $3$ 的子树。