*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 \leq N \leq 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, \dots, 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_{i=1}^{C} (|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\).

Problem credits: Danny Mittal

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.

Problem credits: Danny Mittal

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 containing two integers \(a\) and \(b\)
(\(1 \leq a, b \leq N\)), which denotes an edge between \(a\) and \(b\) in the tree.

The answers for each \(k\) from \(1\) to \(N\) on separate lines.

riseoj 작성

출처 올림피아드 > USACO > 2022-2023 > February > Platinum