题意理解

我们有一棵 $N$ 个节点的树，每个节点有一个标记 $s_i \in \{0,1\}$，$1$ 表示 Bessie 在这个节点看视频，$0$ 表示不看。

我们需要选择若干互不相交的连通块 $c_1, c_2, \dots, c_C$，使得每个 $s_i=1$ 的节点都被某个连通块包含。
$s_i=0$ 的节点可以不在任何连通块中。

一个连通块 $c_i$ 的代价是 $|c_i| + k$，总代价为 $\sum_{i=1}^C (|c_i| + k)$。

我们要对 $k = 1, 2, \dots, N$ 分别求最小总代价。

---

初步分析

设连通块数为 $C$，所有连通块节点数总和为 $S$，那么总代价为： [ S + k \cdot C ]

$S$ 是所有连通块的大小之和，$C$ 是连通块数。

---

等价形式

我们要求： [ \min_{覆盖} \left( \sum_{i} |c_i| + k \cdot C \right) ]

这等价于： [ \min_{覆盖} \left( \sum_{i} (|c_i| + k) \right) ]

---

动态规划思路

考虑在树上做 DP。

设 $dp[u][0]$ 表示节点 $u$ 所在的连通块向上不延伸（即 $u$ 所在连通块在子树内封闭）的最小总代价（只考虑 $u$ 的子树）。

$dp[u][1]$ 表示节点 $u$ 所在的连通块向上延伸（即 $u$ 所在连通块可能和父节点连通）的最小总代价。

---

状态转移

情况 1: $u$ 是标记为 $0$ 的节点

• 如果 $u$ 不在任何连通块中（即 $u$ 不被选入连通块），那么 $u$ 的每个子节点 $v$ 必须自己封闭，即取 $dp[v][0]$。
• 如果 $u$ 在某个连通块中（为了向上延伸），那么 $u$ 必须和至少一个子节点连通，其他子节点可以封闭或也连通。

但注意：$s_u=0$ 的节点可以不在任何连通块，所以 $dp[u][0]$ 可以是不包含 $u$ 的情况。

实际上更简单的定义是：

设：

• $f[u]$：$u$ 子树内，$u$ 不在任何连通块的最小代价
• $g[u]$：$u$ 子树内，$u$ 在某个连通块的最小代价

---

重新定义

更常见的做法是：

$dp[u][0]$：$u$ 不在任何连通块中（那么所有 $s_v=1$ 的子孙必须被覆盖，但 $u$ 不参与连通块）

$dp[u][1]$：$u$ 在某个连通块中，且这个连通块在子树内已经封闭（即不与父节点连通）

$dp[u][2]$：$u$ 在某个连通块中，且这个连通块准备与父节点连通

但这样状态有点多。我们参考类似题目的经典做法：

---

经典 DP 状态

设：

• $dp[u][0]$：$u$ 不在任何连通块，子树内所有 $1$ 节点已被覆盖的最小代价
• $dp[u][1]$：$u$ 在某个连通块中，且该连通块尚未封闭（可以向上延伸）的最小代价
• $dp[u][2]$：$u$ 在某个连通块中，且该连通块已封闭的最小代价

转移：

1. $dp[u][0]$：$u$ 不在连通块
   那么所有子节点 $v$ 必须已封闭（状态 2），因为不能向上延伸到 $u$。
   所以： [ dp[u][0] = \sum_v dp[v][2] ] 但注意：如果 $s_u=1$，那么 $u$ 必须被覆盖，所以 $dp[u][0]$ 不可能（设为无穷大）。

2. $dp[u][1]$：$u$ 在连通块且向上延伸
   那么 $u$ 的连通块至少包含 $u$ 自己，代价目前为 $1$（节点数），$k$ 的代价先不算，最后统一算。
   子节点 $v$ 可以选择：

   • 与 $u$ 连通（状态 1），这样节点数合并，不增加 $k$ 的代价
   • 不连通（状态 2），这样增加一个连通块，代价增加 $dp[v][2]$

   我们要最小化 $\sum$ 节点数 + $k \times$ 连通块数。
   设 $x$ 是与 $u$ 连通的子节点数，那么： [ dp[u][1] = 1 + \sum_v \min(dp[v][1], dp[v][2] + k) ] 因为与 $u$ 连通的子节点用 $dp[v][1]$（不增加 $k$，节点数合并），不连通的用 $dp[v][2]$（增加 $k$ 代价）。

3. $dp[u][2]$：$u$ 在连通块且封闭
   有两种可能：

   • $u$ 单独一个连通块：代价 $1 + k$，子节点全部取 $dp[v][2]$
   • $u$ 与至少一个子节点连通，然后封闭：那么选一个子节点 $v$ 用 $dp[v][1]$（与 $u$ 连通），其他子节点用 $\min(dp[v'][1], dp[v'][2]+k)$？不对，这样复杂。

   实际上更简单：$dp[u][2] = \min(1 + k + \sum_v dp[v][2],\; dp[u][1])$
   但 $dp[u][1]$ 可能比 $dp[u][2]$ 小吗？不一定，因为 $dp[u][1]$ 没算封闭的 $k$ 代价。

   正确做法：

   • 要么 $u$ 单独成块：$1 + k + \sum dp[v][2]$
   • 要么 $u$ 与子节点连通并在某个子树封闭：这其实包含在 $dp[u][1]$ 的某个分支里？不，$dp[u][1]$ 是向上开放的。

   所以 $dp[u][2] = \min(1 + k + \sum_v dp[v][2],\; \min\limits_v [dp[v][2] - \min(dp[v][1], dp[v][2]+k) + dp[u][1]])$？太复杂。

---

更简洁的状态（常见解法）

设：

• $dp[u][0]$：$u$ 不在连通块，子树内所有 $1$ 被覆盖
• $dp[u][1]$：$u$ 在连通块且连通块可能向上延伸
• 最终封闭的块在根节点处理

转移：

1. $dp[u][0]$：
   如果 $s_u=1$，不可能（inf）。
   否则 $dp[u][0] = \sum_v \min(dp[v][0], dp[v][1] + k)$？
   不对，如果 $u$ 不在块，子节点可以单独成块（$dp[v][1]+k$）或不在块（$dp[v][0]$），但必须覆盖所有 $1$。

   其实 $dp[u][0] = \sum_v dp[v][1] + k$？
   因为 $u$ 不在块，每个子节点必须自己成块（$dp[v][1]$ 表示 $v$ 在块且开放，但 $v$ 必须封闭，所以应该是 $dp[v][1] + k$？）
   实际上 $dp[v][1]$ 已经包含 $v$ 所在块的节点数，但没加 $k$，所以加 $k$ 表示 $v$ 单独成块。

   所以： [ dp[u][0] = \sum_v (dp[v][1] + k) ] 但这样可能多算 $k$？因为每个子节点都成块。

2. $dp[u][1]$：
   $u$ 在块，节点数至少 1。
   子节点可以选择：

   • 与 $u$ 连通：用 $dp[v][1]$（不加 $k$）
   • 不与 $u$ 连通：用 $dp[v][1] + k$（单独成块）或 $dp[v][0]$（不在块，但必须 $s_v=0$ 才能不在块）

   所以： [ dp[u][1] = 1 + \sum_v \min(dp[v][1],; dp[v][1]+k,; dp[v][0]) ] 但 $dp[v][1] \le dp[v][1]+k$，所以去掉第二个。
   所以： [ dp[u][1] = 1 + \sum_v \min(dp[v][1], dp[v][0]) ] 注意 $dp[v][0]$ 只在 $s_v=0$ 时有限，否则无穷大。

---

初始化

叶子节点：

• 如果 $s_u=1$：$dp[u][0] = \inf$, $dp[u][1] = 1$（自己成块）
• 如果 $s_u=0$：$dp[u][0] = 0$, $dp[u][1] = 1$（可以成块，也可以不成块，但 $dp[u][1]$ 是成块的情况）

---

最终答案

根节点（任意根）的答案： [ ans = \min(dp[root][0], dp[root][1] + k) ] 因为如果根在块且开放，则必须封闭（加 $k$）。

---

对 $k$ 的处理

我们要对 $k=1..N$ 都求答案。
观察转移中 $k$ 只出现在 $dp[u][0]$ 的 $\sum (dp[v][1]+k)$ 和最后的 $ans$ 中。

实际上 $dp[u][0] = \sum (dp[v][1]+k) = \sum dp[v][1] + deg(u) \cdot k$。

所以 $dp$ 是关于 $k$ 的线性函数，可以证明 $dp[u][0]$ 和 $dp[u][1]$ 都是关于 $k$ 的分段线性凸函数，段数是 $O(n)$。

因此可以用凸包优化或直接枚举 $k$ 做 $O(n)$ 次 DP，总复杂度 $O(n^2)$ 对于 $n\le 200000$ 太大。

---

优化

注意到 $C$（连通块数）不会超过 $1$ 的个数，并且随着 $k$ 增大，$C$ 单调不增。
因此可以按 $C$ 分类，对每个可能的 $C$ 求出最小的 $S$，然后总代价 $S + kC$ 取 $\min$。

这个思路是：
对于固定的 $C$，我们想要最小化 $S$（覆盖所有 $1$ 的 $C$ 个连通块的总大小）。
那么问题变成：选 $C$ 个连通块覆盖所有 $1$，最小化总节点数。

这个可以用贪心/树形 DP 求出 $minSize[C]$。

然后 $ans(k) = \min_{C=1}^{m} (minSize[C] + k \cdot C)$。

$minSize[C]$ 关于 $C$ 是凸的？可以证明是的。
因此可以斜率优化，$O(n)$ 求出所有 $k$ 的答案。

---

最终算法（思路）

1. 求出 $minSize[C]$ 表示用 $C$ 个连通块覆盖所有 $1$ 的最小总大小。
2. $ans(k) = \min_{C} (minSize[C] + kC)$。
3. 输出 $ans(1) \dots ans(N)$。

求 $minSize[C]$ 可以用树形 DP 合并凸包的方法（难度较大），但本题 $n\le 2\times 10^5$，需要 $O(n \log n)$ 或 $O(n)$ 做法。

---

算法标签
树形DP 凸优化 斜率优化 连通块覆盖