#PU1310. USACO 2023 February Contest, Platinum — Problem 3. Watching Cowflix

USACO 2023 February Contest, Platinum — Problem 3. Watching Cowflix

USACO 2023 February Contest, Platinum — Problem 3. Watching Cowflix

题目描述

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 NN (2≤N≤2⋅1052 \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 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 c1,c2,…,cCc_1, c_2, \dots, c_C so that every node where Bessie watches Cowflix must be contained within some cic_i. The cost of the set of components is ∑i=1C(∣ci∣+k)\sum_{i=1}^{C} (|c_i|+k), where ∣ci∣|c_i| is the number of nodes in component cic_i. Nodes where Bessie does not watch Cowflix do not have to be in any cic_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 s1s2s3…sNs_1s_2s_3 \dots s_N where si=1s_i = 1 if Bessie watches Cowflix at node ii. Then N−1N-1 lines follow, each containing two integers aa and bb (1≤a,b≤N1 \leq a, b \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.

数据范围

Inputs 3-5: N≤5000N\le 5000 Inputs 6-8: ii is connected to i+1i+1 for all i∈[1,N)i\in [1,N). Inputs 9-19: N≤105N\le 10^5 Inputs 20-24: No additional constraints. Problem credits: Danny Mittal

样例

样例 1

5
10001
1 2
2 3
3 4
4 5
4
6
8
9
10
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\}$.

样例 2

7
0001010
7 4
5 6
7 2
5 1
6 3
2 5
4
6
8
9
10
11
12