题目描述

题目译自 USACO 2023 February Contest, Platinum Problem 3. Watching Cowflix

Bessie 喜欢看牛飞上的视频，并且她会在一些不同的地方看视频。FJ 的农场可以用一棵有 $N\ (2\le N\le 2\cdot 10^5)$ 个节点的树来表示，并且对于每个节点，要么 Bessie 在这里看牛飞，要么不看。保证 Bessie 至少在一个节点处看牛飞。

不幸的是，牛飞推出了一个新的订阅模式以打击密码共享。在这个新模式中，你可以选择农场中一个大小为 $d$ 的连通分量，支付 $d+k$ 块钱后，这个账号才能在这个连通分量中使用。形式化地说，你需要选择一组互不相交的连通分量 $c_1,c_2,\ldots,c_C$ 使得每个 Bessie 会在其上看牛飞的节点包含在某个 $c_i$ 中。这组连通分量的花费为 $\sum_{i=1}^C (|c_i|+k)$，其中 $|c_i|$ 指连通分量 $c_i$ 中的节点个数。Bessie 不会在其上看牛飞的节点不需要包含在任何 $c_i$ 中。

Bessie 担心新的订阅模式对于她会到的地方来说太贵了，所以她在想要不要改用哞芦。为了帮助她进行决策，请计算如果保持她的浏览习惯的话，使用牛飞最少要支付多少钱。因为牛飞并未公布 $k$ 的值，请计算对于 $k$ 取从 $1$ 到 $N$ 的所有整数时的答案。

输入格式

第一行一个整数 $N$。

第二行一个二进制串 $s_1s_2s_3\ldots s_N$，其中如果 Bessie 会在节点 $i$ 处看牛飞的话，$s_i=1$。

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

输出格式

输出 $N$ 行，第 $i$ 行表示 $k=i$ 时的答案。

5
10001
1 2
2 3
3 4
4 5

4
6
8
9
10

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

4
6
8
9
10
11
12

数据范围与提示

• 3-5 组数据：$N\le 5\ 000$
• 6-8 组数据：对于所有 $i\in [1,N)$，$i$ 与 $i+1$ 有边相连
• 9-19 组数据：$N\le 10^5$
• 20-24 组数据：无附加限制