Bessie 喜欢在 Cowflix 上看节目，而且她会在不同的地方观看。Farmer John 的农场可以表示为一棵有 $N$ ($2 \leq N \leq 2\cdot 10^5$) 个节点的树，对于每个节点，Bessie 要么在那里看 Cowflix，要么不看。保证 Bessie 至少在一个节点上看 Cowflix。

不幸的是，Cowflix 正在引入一种新的订阅模式来打击密码共享。在这种新模式下，你可以选择农场中一个大小为 $d$ 的连通分量，然后你需要支付 $d + k$ 个 moonies 来获得一个可以在该连通分量中使用的账户。形式化地说，你需要选择一组不相交的连通分量 $c_1, c_2, \dots, c_C$，使得 Bessie 观看 Cowflix 的每个节点都必须包含在某个 $c_i$ 中。这组分量的总成本为 $\sum_{i=1}^{C} (|c_i|+k)$，其中 $|c_i|$ 是连通分量 $c_i$ 中的节点数。Bessie 不看 Cowflix 的节点不必包含在任何 $c_i$ 中。

Bessie 担心新的订阅模式对她来说太贵了，她正在考虑改用 Mooloo。为了帮助她做决定，请计算她为了维持观看习惯需要支付给 Cowflix 的最低金额。由于 Cowflix 尚未公布 $k$ 的值，请计算所有 $k$ 从 $1$ 到 $N$ 的整数值对应的结果。

输入格式

第一行包含 $N$。

第二行包含一个位字符串 $s_1s_2s_3 \dots s_N$，其中如果 Bessie 在节点 $i$ 观看 Cowflix，则 $s_i = 1$。

接下来 $N-1$ 行，每行包含两个整数 $a$ 和 $b$ ($1 \leq a, b \leq N$)，表示树中 $a$ 和 $b$ 之间的一条边。

输出格式

对于每个 $k$ 从 $1$ 到 $N$，在单独的行中输出答案。

样例

样例输入 1

5
10001
1 2
2 3
3 4
4 5

样例输出 1

4
6
8
9
10

说明 1

对于 $k\le 3$，最优方案是拥有两个账户：$c_1 = \{1\}, c_2 = \{5\}$。对于 $k\ge 3$，最优方案是拥有一个账户：$c_1 = \{1, 2, 3, 4, 5\}$。

样例输入 2

7
0001010
7 4
5 6
7 2
5 1
6 3
2 5

样例输出 2

4
6
8
9
10
11
12

子任务

• 输入 3-5：$N\le 5000$
• 输入 6-8：对于所有 $i\in [1,N)$，$i$ 与 $i+1$ 相连。
• 输入 9-19：$N\le 10^5$
• 输入 20-24：无额外限制。