Watching Cowflix

题目描述

注意：本题时间限制为 3s，是默认时间限制的 1.5 倍。 Bessie 喜欢在 Cowflix 上看剧，并且她会在不同的地点观看。Farmer John 的农场可以表示为一棵有 $N$（$2 \leq N \leq 2\cdot 10^5$）个节点的树，并且对每个节点，要么 Bessie 会在那里观看 Cowflix，要么不会。保证 Bessie 至少在一个节点观看 Cowflix。

不幸的是，为了打击密码共享，Cowflix 正在推出一种新的订阅模式。在新模式中，你可以在农场中选择一个大小为 $d$ 的连通块，然后你需要为一个只能在该连通块中使用的账号支付 $d + k$ 个 moonies。形式化地说，你需要选择一组两两不相交的连通块 $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$ 时表示 Bessie 在节点 $i$ 观看 Cowflix。 接下来有 $N-1$ 行，每行包含两个整数 $a$ 和 $b$（$1 \leq a, b \leq N$），表示树中 $a$ 与 $b$ 之间有一条边。

输出格式

对每个 $k$ 从 $1$ 到 $N$ 的答案分别输出一行。

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

提示

当 $k\le 3$ 时，最优是开两个账号：$c_1 = \{1\}, c_2 = \{5\}$。当 $k\ge 3$ 时，最优是开一个账号：$c_1 = \{1, 2, 3, 4, 5\}$。 SCORING: Inputs 3-5: $N\le 5000$ Inputs 6-8: 对所有 $i\in [1,N)$，$i$ 与 $i+1$ 相连。 Inputs 9-19: $N\le 10^5$ Inputs 20-24: 无额外限制。 题目作者：Danny Mittal

标签: USACO|2023|Platinum

来源

USACO|2023|Platinum