题目描述

注意：本题的时间限制为 3 秒，是默认时间的 1.5 倍。

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

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

Bessie 担心新的订阅模式可能对她来说太贵，因为她访问的地方很多，因此她考虑转向 Mooloo。为了帮助她做出决定，计算她需要支付给 Cowflix 的最低金额以维持她的观看习惯。因为 Cowflix 尚未公布 $k$ 的值，所以计算从 $1$ 到 $N$ 的所有整数值的 $k$。

输入格式

第一行包含 $N$。

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

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

输出格式

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

输入输出样例 #1

输入 #1

5
10001
1 2
2 3
3 4
4 5

输出 #1

4
6
8
9
10

输入输出样例 #2

输入 #2

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

输出 #2

4
6
8
9
10
11
12

说明/提示

示例 1 的解释

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

评分

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

题面翻译由 ChatGPT-4o 提供。