题目描述

Note: The time limit for this problem is 3s, 1.5x the default.

Bessie likes to watch shows on Cowflix, and she watches them in different places. Farmer John's farm can be represented as a tree with $N(2 \le N \le 2 \cdot 10^5)$ nodes, and for each node, either Bessie watches Cowflix there or she doesn't. It is guaranteed that Bessie watches Cowflix in at least one node.

Unfortunately, Cowflix is introducing a new subscription model to combat password sharing. In their new model, you can choose a connected component of size $d$ in the farm, and then you need to pay $d+k$ moonies for an account that you can use in that connected component. Formally, you need to choose a set of disjoint connected components $c_1,c_2, \cdots ,c_C$ so that every node where Bessie watches Cowflix must be contained within some $c_i$. The cost of the set of components is $\sum\limits^{C}_{i=1}(|c_i|+k)$, where $|c_i|$ is the number of nodes in component $c_i$. Nodes where Bessie does not watch Cowflix do not have to be in any $c_i$.

Bessie is worried that the new subscription model may be too expensive for her given all the places she visits and is thinking of switching to Mooloo. To aid her decision-making, calculate the minimum amount she would need to pay to Cowflix to maintain her viewing habits. Because Cowflix has not announced the value of $k$, calculate it for all integer values of $k$ from $1$ to $N$.

输入格式

The first line contains $N$.

The second line contains a bit string $s_1s_2s_3\cdots s_N$ where $s_i=1$ if Bessie watches Cowflix at node $i$.

Then $N - 1$ lines follow, each containing two integers $a$ and $b (1 \le a,b \le N)$, which denotes an edge between $a$ and $b$ in the tree.

输出格式

The answers for each $k$ from $1$ to $N$ on separate lines.

题目大意

Bessie 喜欢在 Cowflix 上看节目，并且喜欢在农场里的不同地方看。

Farmer John 的农场可以被描述成一颗 $n$ 个节点的树，并且 Bessie 只可能在树上的一些指定的节点处看节目。每个节点是否要看节目将在初始时给定；保证至少在一个节点处会看节目。

不幸的是，Cowflix 为了避免奶牛们使用公用账号，采取了一个新的会员策略：

• Bessie 将多次付款，每次选择树上任意一个大小为 $d$ 的连通块，为其支付 $d+k$ 的代价，才能够在这些位置看节目。

换言之，Bessie 将选取若干连通块 $c_1,c_2,\dots,c_C$，支付 $\sum_{i=1}^C(|c_i|+k)$ 的代价，才可以在这些连通块的各个节点处看节目；即，被指定的节点必须被某个连通块包含，不被指定的节点不必被包含。

Bessie 觉得这个策略的代价太昂贵了，考虑是否要改在 Mooloo 上看节目。为了帮助其决策，你应当告诉之 $k$ 取遍 $1\sim n$ 时看节目的最小总代价。

$1\le n\le2\times10^5$。

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

提示

Explanation for Sample 1

For $k \le 3$, it's optimal to have two accounts: $c_1=\{1\},c_2=\{5\}$. For $k \ge 3$, it's optimal to have one account: $c_1=\{1,2,3,4,5\}$.

SCORING

• Inputs $3-5$: $N \le 5000$
• Inputs $6-8$: $i$ is connected to $i+1$ for all $i \in [1,N)$.
• Inputs $9-19$: $N \le 10^5$
• Inputs $20-24$: No additional constraints.