题目翻译

题目描述

Bessie 喜欢在 FJ 农场的不同地方看 Cowflix 视频。农场有 $N$ 个节点，构成一棵树。每个节点有一个标记 $s_i \in \{0,1\}$，$1$ 表示 Bessie 在这里看视频，$0$ 表示不看。保证至少有一个 $s_i=1$。

Cowflix 推出了新订阅模式：你可以选择若干个互不相交的连通块 $c_1, c_2, \dots, c_C$，覆盖所有标记为 $1$ 的节点（标记为 $0$ 的节点可以不被覆盖）。总花费为： [ \sum_{i=1}^C (|c_i| + k) ] 其中 $|c_i|$ 是连通块 $c_i$ 的节点数，$k$ 是给定的参数。

请对 $k = 1, 2, \dots, N$ 分别计算最小总花费。

---

样例分析

样例 1

5
10001
1 2
2 3
3 4
4 5

树是一条链：1-2-3-4-5，标记为 1 0 0 0 1。

• $k=1$：选两个连通块 $\{1\}$ 和 $\{5\}$，花费 $(1+1)+(1+1)=4$
• $k=2$：同上，花费 $(1+2)+(1+2)=6$
• $k=3$：两个块花费 $(1+3)+(1+3)=8$，一个块花费 $(5+3)=8$，取 $8$
• $k=4$：一个块花费 $5+4=9$
• $k=5$：一个块花费 $5+5=10$

输出：

4
6
8
9
10

---

问题转化

设连通块数为 $C$，所有连通块节点数总和为 $S$，则总花费为： [ S + k \cdot C ]

目标：对每个 $k$，最小化 $S + kC$。

---

关键观察

1. 连通块数 $C$ 的范围：$1 \le C \le m$，其中 $m$ 是标记为 $1$ 的节点数。
2. 单调性：随着 $k$ 增大，最优的 $C$ 单调不增（因为大 $k$ 倾向于减少连通块数）。
3. 问题分解：对于固定 $C$，我们需要找到覆盖所有 $1$ 的 $C$ 个连通块，使得总节点数 $S$ 最小。

---

固定 $C$ 的子问题

定义 $f(C)$ = 用 $C$ 个连通块覆盖所有 $1$ 的最小总节点数。

那么： [ ans(k) = \min_{C=1}^m [f(C) + k \cdot C] ]

---

求 $f(C)$ 的树形 DP

在树上，我们定义 DP 状态：

• $dp[u][0]$：$u$ 不在任何连通块中，子树内所有 $1$ 被覆盖的最小总节点数（和连通块数）
• $dp[u][1]$：$u$ 在某个连通块中，且该连通块可以向上延伸（即与父节点连通）的最小总节点数（和连通块数）

但这里我们需要同时记录节点数和连通块数，因为要权衡 $S$ 和 $C$。

---

状态设计

设 $dp[u][t]$ 表示在 $u$ 的子树中：

• $t=0$：$u$ 不在任何连通块
• $t=1$：$u$ 在连通块且该连通块未封闭（可连父节点）
• $t=2$：$u$ 在连通块且该连通块已封闭

但 $t=2$ 可以通过 $t=1$ 加上 $k$ 代价得到，所以可以简化。

实际上更常见的做法是：
设 $F_u(x)$ 表示在 $u$ 子树中，假设 $u$ 所在连通块未封闭，使用 $x$ 个连通块的最小总节点数（$x \ge 1$ 如果 $u$ 在块中）。
但这样状态是 $O(n^2)$ 的，不可行。

---

凸性优化

重要性质：$f(C)$ 是关于 $C$ 的凸函数。
即 $f(C) - f(C-1) \le f(C+1) - f(C)$。

因此，$ans(k) = \min_C [f(C) + kC]$ 可以通过在凸包上求最小值得到。

---

求凸包方法

我们可以在树上做 DP，用 std::vector<std::pair<int, int>> 存储 (连通块数, 总节点数) 的凸包。

合并子节点时，用杨氏卷积（min-plus convolution）合并凸包。

---

算法步骤

1. 树形 DP：
   对每个节点 $u$，维护一个凸包 $h_u$，表示在 $u$ 子树中，$u$ 在连通块内且连通块未封闭时，不同连通块数对应的最小总节点数。

   初始化：

   • 如果 $s_u=1$：$h_u = \{(1,1)\}$（一个连通块，节点数 1）
   • 如果 $s_u=0$：$h_u = \{(0,0)\}$（不在块）

2. 合并子节点：
   对于 $u$ 的子节点 $v$，合并 $h_u$ 和 $h_v$：

   • 如果 $u$ 与 $v$ 连通：卷积 $h_u$ 和 $h_v$（连通块数相加，节点数相加）
   • 如果 $u$ 不与 $v$ 连通：卷积 $h_u$ 和 $(h_v + (1,k))$，其中 $h_v + (1,k)$ 表示 $v$ 单独成块（块数 +1，节点数不变，但这里节点数已经包含在 $h_v$ 中）

   实际上更简单：定义两个凸包：

   • $in_u$：$u$ 在连通块内且未封闭
   • $out_u$：$u$ 不在连通块内

   转移：

   • $out_u = \bigotimes_v (in_v + (1,0))$（每个子节点单独成块，块数+1，节点数不变？不对，节点数要加 $|c_v|$） 这里需要细致处理。

3. 最终答案：
   根节点的凸包 $in_{root}$ 和 $out_{root}$ 合并（$out_{root}$ 只在根为 0 时有效，否则必须选根）。
   得到全树凸包 $H$，则 $ans(k) = \min_{(C,S) \in H} (S + kC)$。

---

时间复杂度

凸包合并用杨氏卷积，复杂度 $O(n \log n)$ 或 $O(n)$（用凸包斜率技巧）。
总复杂度 $O(n \log n)$ 或 $O(n)$，可过 $n \le 2\times 10^5$。

---

代码框架（省略实现细节）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Line {
    ll m, b; // y = m*x + b
    // 这里 m = 连通块数, b = 总节点数
};

vector<Line> merge(const vector<Line>& a, const vector<Line>& b) {
    // 杨氏卷积合并凸包
}

vector<Line> add(const vector<Line>& a, const vector<Line>& b) {
    // 对应位置相加
}

int main() {
    int N;
    string s;
    cin >> N >> s;
    vector<vector<int>> g(N);
    for (int i = 0; i < N-1; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    // 树形 DP
    function<vector<Line>(int, int)> dfs = [&](int u, int p) {
        vector<Line> dp_in, dp_out;
        if (s[u] == '1') {
            dp_in = {{1, 1}}; // 一个连通块，总节点数 1
            dp_out = {}; // 不可能
        } else {
            dp_in = {{1, 1}}; // 可以成块
            dp_out = {{0, 0}}; // 可以不成块
        }

        for (int v : g[u]) {
            if (v == p) continue;
            auto ch_in = dfs(v, u);
            auto ch_out = ...; // ch_in 每个块数+1

            // 合并
            auto new_in = merge(add(dp_in, ch_in), ...);
            auto new_out = merge(add(dp_out, ch_in), ...);
            dp_in = new_in;
            dp_out = new_out;
        }
        return ...;
    };

    auto hull = dfs(0, -1);
    for (int k = 1; k <= N; k++) {
        ll ans = 1e18;
        for (auto [C, S] : hull) {
            ans = min(ans, S + k * C);
        }
        cout << ans << "\n";
    }
}

---

总结

本题考察了：

• 树形动态规划
• 凸优化（凸包合并）
• 斜率优化求最小值
• 问题转化为固定连通块数的最小总节点数

关键点在于发现 $f(C)$ 的凸性，从而用凸包合并高效求解。

---

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