Watching Cowflix

문제

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 $NN$ ($2\le N\le 2\cdot {10}^{5}2\; \backslash leq\; N\; \backslash leq\; 2\backslash 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 $dd$ in the farm, and then you need to pay $d+kd\; +\; 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,\dots ,c_{C}c\_1,\; c\_2,\; \backslash dots,\; c\_C$ so that every node where Bessie watches Cowflix must be contained within some $c_{i}c\_i$. The cost of the set of components is ${\sum }_{i=1}^C(\mathrm{\mid }{c}_i\mathrm{\mid }+k)\backslash sum\_\{i=1\}^\{C\}\; (|c\_i|+k)$, where $\mathrm{\mid }{c}_i\mathrm{\mid }|c\_i|$ is the number of nodes in component $c_{i}c\_i$. Nodes where Bessie does not watch Cowflix do not have to be in any $c_{i}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 $kk$, calculate it for all integer values of $kk$ from $11$ to $NN$.

입력

The first line contains $NN$.

The second line contains a bit string $s_1{s}_2{s}_3\dots s_{N}s\_1s\_2s\_3\; \backslash dots\; s\_N$ where $s_i=1s\_i\; =\; 1$ if Bessie watches Cowflix at node $ii$.

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

출력

The answers for each $kk$ from $11$ to $NN$ on separate lines.

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