Cowflix 시청하기

Bessie는 Cowflix 시청을 좋아하며, 여러 장소에서 시청합니다. Farmer John의 농장은 $N$ ($2 \leq N \leq 2\cdot 10^5$)개의 정점으로 이루어진 트리입니다. 각 정점에서 Bessie는 Cowflix를 보거나, 보지 않습니다. 적어도 한 정점에서는 Bessie가 Cowflix를 본다고 보장됩니다.

Cowflix는 비밀번호 공유를 막기 위해 새로운 구독 모델을 도입합니다. 새 모델에서는 농장에서 크기가 $d$인 연결 성분 하나를 고르고, 그 성분에서 쓸 수 있는 계정에 대해 $d + k$ 무니를 냅니다. 형식적으로 말하면, 서로 겹치지 않는 연결 성분 $c_1, c_2, \dots, c_C$를 고르되, Bessie가 Cowflix를 보는 모든 정점이 어떤 $c_i$에 포함되도록 해야 합니다. 집합의 비용은 $\sum_{i=1}^{C} (|c_i|+k)$이며, 여기서 $|c_i|$는 $c_i$의 정점 수입니다. Bessie가 Cowflix를 보지 않는 정점은 어떤 $c_i$에도 포함될 필요가 없습니다.

Bessie는 새 모델이 자신의 시청 습관에 비해 너무 비쌀까 걱정하며, Mooloo로 바꾸는 것도 고려하고 있습니다. 판단을 돕기 위해, 시청 습관을 유지하려면 Cowflix에 최소 얼마를 내야 하는지 계산하세요. Cowflix는 아직 $k$ 값을 발표하지 않았으므로, $1$부터 $N$까지 모든 정수 $k$에 대해 답을 구하세요.

첫 줄에 $N$이 주어집니다. 둘째 줄에는 비트 문자열 $s_1s_2s_3 \dots s_N$이 주어지며, $s_i = 1$이면 정점 $i$에서 Bessie가 Cowflix를 봅니다. 이후 $N-1$개의 줄에 정수 $a$, $b$ ($1 \leq a, b \leq N$)가 하나씩 주어지며, 이는 트리에서 $a$와 $b$를 잇는 간선을 뜻합니다.

$k$가 $1$부터 $N$까지일 때의 답을 한 줄에 하나씩 출력합니다.