题目描述

小 $\clubsuit$ 是 OI 国马拉松协会的会长。有一天，他打算举办全国青少年马拉松奥林匹克联赛（National Olympiad in Marathon in Provinces, NOMP），于是准备在 OI 国中修建一条赛道。

OI 国有 $n$ 个城市，一共有 $n - 1$ 条道路将它们连通。也就是说，OI 国的结构是一棵树。

小 $\clubsuit$ 会选择一个城市作为起点，再选择一个城市作为终点，这样赛道的长度就等于起点到终点路径上的边数。由于 OI 国的群众非常懒，所以赛道长为 $0$ 也是允许的。

由于一些特殊原因，赛道的终点只能是一些特定的城市，而赛道的起点可以是任意一个城市。

现在小 $\clubsuit$ 想知道：对于每个城市，如果选择它作为起点，那么赛道的长度有几种可能的取值？

输入格式

第一行一个整数 $n$。

接下来一行 $n$ 个整数，第 $i$ 个整数如果为 $0$，表示城市 $i$ 不能作为终点；如果为 $1$，表示城市 $i$ 可以作为终点。

接下来 $n - 1$ 行，每行两个整数 $u, v$($1 \le u, v \le n$)，表示有一条连接城市 $u$ 和城市 $v$ 的道路。

输出格式

输出 $n$ 行，第 $i$ 行一个整数，表示如果选择城市 $i$ 作为赛道的起点，赛道的长度有几种可能的取值。

样例

input

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

output

3
2
3
3
3
2

数据范围与提示

子任务一：$n = 2000$，$30$ 分；
子任务二：$n = 50000$，$70$ 分。