题目描述

Bob 是一名探险协会的主席，最近他想为即将举行的探险挑战赛规划路线。比赛场地位于一座森林公园中，公园里共有 $n$ 个景点，并且有 $n-1$ 条道路将这些景点连成一棵树的结构。

比赛需要设定一个起点和一个终点，路线长度为起点到终点之间经过的道路数目。特殊的是，终点只能在部分指定的景点中选择，而起点则可以是任意景点（包括终点本身，即路线长度允许为 $0$）。

现在 Bob 希望知道，对于森林公园中的每个景点，如果选它作为起点，比赛路线的长度有多少种不同的可能？

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数，第 $i$ 个整数 $a_i$ 如果为 $0$，表示景点 $i$ 不能作为赛道终点；如果为 $1$ 表示可以。

接下来 $n-1$ 行，每行两个整数 $u,v$ 表示一条连接景点 $u,v$ 的道路。

输出格式

共 $n$ 行，第 $i$ 行一个整数表示以景点 $i$ 作为起点得到的长度种类数。

6
1 0 1 0 1 0
1 2
2 3
3 4
3 5
2 6

3
2
3
3
3
2

数据范围

对于 $30\%$ 的数据，$1\leq n\leq 2000$。

对于 $60\%$ 的数据，$1\leq n\leq 10000$。

对于 $100\%$ 的数据，$1\leq n\leq 50000$，$a_i\in\{0,1\}$，$1\leq u,v\leq n$，$u\neq v$。