Watching Cowflix

Bessie likes watching shows on Cowflix, and she watches them in different places. Farmer John's farm is a tree with $N$ ($2 \leq N \leq 2\cdot 10^5$) nodes. Each node is either a place where Bessie watches Cowflix or a place where she does not. At least one node is a place where Bessie watches Cowflix.

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

Bessie is worried the new model may be too expensive for her viewing habits, and she is considering switching to Mooloo. To help her decide, calculate the minimum amount she must pay Cowflix to keep her viewing habits. Cowflix has not announced $k$, so calculate the answer for every integer $k$ from $1$ to $N$.

The first line contains $N$. The second line contains a bit string $s_1s_2s_3 \dots s_N$, where $s_i = 1$ if Bessie watches Cowflix at node $i$. Then $N-1$ lines follow, each with two integers $a$ and $b$ ($1 \leq a, b \leq N$), denoting an edge between $a$ and $b$ in the tree.

Print the answers for each $k$ from $1$ to $N$, one per line.