题目描述

给一个 $n（1\leq n \leq 10^5）$ 个节点的树，每个节点是白色或者黑色。

一个子树是指，树中选取一些边和点，能组成一个连通块。

一个子树的价值是，白色点的数量减去黑色点的数量。

对于每一个节点，求包含该节点的子树的价值。

输入格式

第一行，两个整数 $n$。

第二行 $n$ 个整数，表示节点的颜色，$0$ 代表黑色，$1$ 代表白色。

接下来 $n-1$行，描述一条边。

输出格式

$n$ 个整数，表示每个节点的答案。

样例输入1

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

样例输出1

2 2 2 2 2 1 1 0 2