形式化题目

给定一棵 $n$ 个节点的树，节点 1 已被感染。传播按"代"同步进行：

• 第 0 代只有节点 1 感染；
• 每代开始时，可以切断一条连接已感染节点与其尚未感染孩子的边（全局至多一条）；随后所有"已感染节点—未切断边—健康节点"同时传播，健康节点成为该代感染者；
• 当没有健康节点可被继续感染时，传播停止。

求一种逐代切断的顺序，使最终感染的节点总数最少，输出这个最小值。

样例的树与一种最优切断顺序如下（先切 $1\text{-}2$，再切 $3\text{-}6$）：

flowchart TB
    N1(("1<br>已感染")) --- N2(("2"))
    N1 --- N3(("3"))
    N2 --- N4(("4"))
    N2 --- N5(("5"))
    N3 --- N6(("6"))
    N3 --- N7(("7"))

第 1 代候选边是 $\{1\text{-}2,\,1\text{-}3\}$，切断 $1\text{-}2$ 后只有 3 被感染；第 2 代候选边是 $\{3\text{-}6,\,3\text{-}7\}$，切断 $3\text{-}6$ 后 7 被感染；第 3 代 7 没有孩子，传播停止。感染集合 $\{1,3,7\}$ 共 3 人，与输出一致。

一个容易被忽略的点：切断机会与"代"绑定。孩子边只能在父节点被感染的下一代被切断——那一代没切，孩子就永久感染，之后再无切断价值。因此第 $k$ 代的候选边恰好是"第 $k-1$ 代新感染者的孩子边"，我们称这个集合为该层的前沿。切断 $u$ 与父节点之间的边，就能保住以 $u$ 为根的整棵子树，于是：

问题转化为：逐层在前沿中选一条边切断，最大化被切断子树的大小之和。

正解

思路

朴素做法：每层枚举所有候选边递归。 拿到本层前沿 $F$，逐个尝试切断 $u \in F$：本层救下 $\mathrm{size}[u]$，下一层前沿变成"其余前沿节点的孩子" $\bigcup_{v \in F \setminus \{u\}} \mathrm{children}(v)$，递归到前沿为空时结算、取最大。做法正确，但搜索树是各层分支数的连乘——一层有 $f$ 条候选边、连续 $d$ 层就是 $f^d$ 条路径，$n = 300$ 时轻松构造出天文数字级的路径数，必然超时。

第一反应的优化是贪心：每层切断子树最大的候选。它不正确。 反例是一棵 $n = 24$ 的树：根的两个孩子中，$A$ 只有一个孩子 $a_1$、$a_1$ 挂 10 片叶子（$\mathrm{size}(A) = 12$），$B$ 直接挂 10 片叶子（$\mathrm{size}(B) = 11$）。

贪心先切 $A$，把 $B$ 留进感染区，第 2 层候选只剩 10 片孤叶，每层最多救 1；先切 $B$，第 2 层前沿只剩 $\{a_1\}$，可以整棵切掉。当前层的收益和未来层会长出什么候选耦合，逐层贪心看不到未来，只能搜索。

关键观察：决策只依赖本层前沿。 切断选择影响的只有下一层前沿，与更早的历史无关——不同切断路径会汇聚到同一个前沿集合，它们的后续最优收益完全相同。朴素搜索慢不是状态多，而是把同一个子问题沿不同路径算了无数遍。于是把"前沿为 $F$ 时，之后每层各切一条边最多救下多少人"定义为记忆化对象：

其中 $\mathrm{kids}(F) = \bigcup_{u \in F} \mathrm{children}(u)$ 是"不切断时"的下一层候选；切断 $u$ 后，它的孩子随子树一起出局，所以下一层前沿是 $\mathrm{kids}(F) \setminus \mathrm{children}(u)$。

两个细节把递推钉死：

1. 每层必切，不切不会更好。 若某层不切，全部前沿感染。对任意候选 $u$：切断立得 $\mathrm{size}[u]$；不切的方案里，$u$ 子树内部未来的切断互不相交，总收益至多 $\sum_{c \in \mathrm{children}(u)} \mathrm{size}[c] = \mathrm{size}[u] - 1$，且 $u$ 自己必然感染；而其余区域的切断序列沿各自的祖先链进行，与 $u$ 子树互不干扰，可以原样保留。所以"切一条"逐层替换总不劣，递推只需枚举切断选择。
2. 原问题的答案：初始前沿是根的孩子，$\text{感染人数} = n - \mathrm{saved}(\mathrm{children}(1))$。

把样例代入递推，就是下面这张状态表（行即 saved 的三个缓存状态）：

最终 $7 - \mathrm{saved}(\{2,3\}) = 7 - 4 = 3$。这正是一棵"DFS 按层枚举切断选择"的搜索树，@cache 把到达同一前沿的分支合并、只保留最优值——等价于对搜索树做最优性剪枝：先算出的状态直接复用，后续到达该状态的分支不再展开。

实现上的最后一块拼图是位图。 $n \leqslant 300$，前沿集合用一个 Python 大整数编码（第 $i$ 位为 1 表示节点 $i$ 在前沿中）：累 $\mathrm{kids}(F)$ 是按位或，转移 nxt & ~kids[u] 是按位与非，取位下标靠 m & -m 取最低位——全部是机器字级操作，与 C++ bitset 解法同阶。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 305;

int n, p;
vector<int> adj[MAXN];
int parent_[MAXN];
vector<int> order;          // 层序
vector<int> children[MAXN];
int size_[MAXN];
bitset<MAXN> kids_mask[MAXN];   // 各点孩子的位图

// bits(mask)：依次产出位图 mask 中为 1 的节点下标
vector<int> bits_of(const bitset<MAXN>& mask) {
    vector<int> res;
    for (int i = 0; i < n; i++)
        if (mask[i]) res.push_back(i);
    return res;
}

// 记忆化（用字符串作为 key）
map<string, int> memo;

int saved(const bitset<MAXN>& frontier) {
    if (frontier.none()) return 0;
    string key = frontier.to_string();
    map<string, int>::iterator it = memo.find(key);
    if (it != memo.end()) return it->second;

    // 本层除被切断点外其余候选全部感染，下一层候选 = 这些点的孩子
    bitset<MAXN> nxt;
    for (int u = 0; u < n; u++)
        if (frontier[u]) nxt |= kids_mask[u];

    int best = 0;
    for (int u = 0; u < n; u++) {
        if (!frontier[u]) continue;
        bitset<MAXN> rest = nxt & ~kids_mask[u];
        int v = size_[u] + saved(rest);
        if (v > best) best = v;
    }
    memo[key] = best;
    return best;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> p;
    for (int i = 0; i < p; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i = 0; i < n; i++) parent_[i] = -1;
    order.push_back(0);
    for (size_t idx = 0; idx < order.size(); idx++) {
        int u = order[idx];
        for (size_t i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i];
            if (v && parent_[v] < 0) {
                parent_[v] = u;
                order.push_back(v);
            }
        }
    }
    for (int v = 1; v < n; v++) children[parent_[v]].push_back(v);
    for (int u = 0; u < n; u++) size_[u] = 1;
    for (int i = (int)order.size() - 1; i >= 0; i--) {
        int u = order[i];
        for (size_t j = 0; j < children[u].size(); j++)
            size_[u] += size_[children[u][j]];
    }
    for (int u = 0; u < n; u++)
        for (size_t j = 0; j < children[u].size(); j++)
            kids_mask[u].set(children[u][j]);

    cout << n - saved(kids_mask[0]) << "\n";
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 06:19
# update_at: 2026-10-02 06:19

import sys
from collections.abc import Iterator
from functools import cache


def bits(mask: int) -> Iterator[int]:
    """依次产出位图 mask 中为 1 的节点下标。"""
    while mask:
        low = mask & -mask
        yield low.bit_length() - 1
        mask ^= low


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    p = next(data)  # 题面的 p：传播途径（边）条数，本题保证是一棵树
    adj: list[list[int]] = [[] for _ in range(n)]
    for _ in range(p):
        a, b = next(data) - 1, next(data) - 1
        adj[a].append(b)
        adj[b].append(a)

    # 以 0 号点（患者 1）为根：边遍历边追加，order 即层序，父一定先于子出现
    parent = [-1] * n
    order = [0]
    for u in order:
        for v in adj[u]:
            if v and parent[v] < 0:  # 根 0 的 parent 永远是 -1，用 v 本身排除
                parent[v] = u
                order.append(v)

    children: list[list[int]] = [[] for _ in range(n)]
    for v in range(1, n):
        children[parent[v]].append(v)

    size = [1] * n  # 以 u 为根的子树人数（含 u 自己）
    for u in reversed(order):
        for v in children[u]:
            size[u] += size[v]

    kids = [sum(1 << v for v in children[u]) for u in range(n)]  # 各点孩子的位图

    @cache
    def saved(frontier: int) -> int:
        """本层可切断候选（位图 frontier）下，之后每层各切一条边最多能保住的人数。"""
        if not frontier:
            return 0
        # 本层除被切断点外其余候选全部感染，下一层候选 = 这些点的孩子
        nxt = 0
        for u in bits(frontier):
            nxt |= kids[u]
        # 每层必切一条：切断 u 保住整棵子树；不切时 u 子树内未来收益至多 size[u]-1
        return max(size[u] + saved(nxt & ~kids[u]) for u in bits(frontier))

    # 最终感染数 = 总人数 - 各层切断子树保住的人数（初始候选是根的孩子）
    print(n - saved(kids[0]))


if __name__ == "__main__":
    solve()

代码分三层：bits 产出位图中的节点下标；saved 承载递推（基例 $F = \varnothing$ 返回 0，否则先按位或累出 $\mathrm{kids}(F)$，再枚举本层每条候选边取最大收益）；solve 只做读入、层序 BFS 建树、逆序算子树大小 size、预计算孩子位图 kids，最后输出 n - saved(kids[0])。注意 BFS 用 if v and parent[v] < 0 同时排除根回边与重复访问；$n = 1$ 时 kids[0] = 0，直接输出 1。

复杂度

• 时间复杂度 $O(S \cdot n)$：$S$ 为可达前沿状态数，每个状态遍历前沿中 $|F|$ 个位做位图合并与缓存查询（Python 大整数位运算按机器字计）。朴素无记忆化搜索是各层分支数的连乘（指数级），记忆化把路径数塌缩成状态数——实测 $n = 300$ 的最大数据 14887 个状态、单测例 $0.309$ 秒，全部 10 组真实数据均低于 $0.31$ 秒，小于 OJ 的 1000ms 限制。
• 空间复杂度 $O(S + n)$：缓存 $S$ 个 int -> int 条目，加 size/kids/children 各 $O(n)$；实测峰值 16.8MB（限制 32MB）。递归深度为传播代数，不超过树高 300，在默认递归上限内。

总结

• 传播按代同步推进，第 $k$ 代的候选切断边恰好是第 $k-1$ 代新感染者的孩子边（前沿），切断 $u$ 与父的边救下以 $u$ 为根的整棵子树，故 $\text{感染人数} = n - \text{各层切断子树大小之和}$。
• 逐层贪心（每层切最大子树）不正确：切断选择决定未来层的候选结构，收益跨层耦合，必须搜索。
• 状态 = 本层前沿集合，转移 = 枚举本层切断哪条边；每层必切（不切的方案可逐层替换成切一条而不变差），递推 $\mathrm{saved}(F) = \max_{u \in F}(\mathrm{size}[u] + \mathrm{saved}(\mathrm{kids}(F) \setminus \mathrm{children}(u)))$。
• 不同切断路径汇聚到相同前沿，functools.cache 记忆化把指数级搜索树合并成可达状态图；前沿用位图编码，转移全是字级位运算。
• 易错点：切断机会只有一次（父节点感染的下一代），不能推迟到更晚的代；$n = 1$ 时输出 1。