思路与算法

把感染树根设为1。一个周期开始时，只有当前已感染结点的尚健康孩子会成为下一代患者。切断更深的边不会优于切断它所在的当前前沿根边，因此只需在待感染子树森林中选择一个根子树整体保护，其余根本周期感染，再把它们的孩子加入下一周期前沿。用自底向上的孩子类型多重集为每种有根子树分配同构类型。状态是当前前沿的类型多重集，同类型根保护任意一个等价。记忆化精确求最少后续感染数；按子树大小优先尝试，并用“本周期必须感染前沿大小减1，加下一周期至少前沿大小减1”作安全下界剪枝。空前沿或只有一个前沿根时都能再感染0人。答案再加初始患者1。

正确性说明

若方案本周期切断某个深处边，改为切断它在当前待感染森林中的根边会保护包含原受保护人群的更大子树，且不增加切断次数；所以总有最优方案切断当前一个根。选定后，本周期其余前沿根必被感染，下一状态恰是这些根的孩子子树构成的森林，过去如何到达该森林不再影响未来。将同构子树合并类型保持全部未来选择、大小和层次关系，故类型多重集是充分状态。递推枚举每个不同类型，取最小后续代价即得全局最优；下界只少算未来感染，不会剪掉更优方案。缓存容量只影响是否复用状态，满后仍正常精确搜索。

复杂度

根树构建、子树类型排序和初始化至多O(n² log n)的保守界。设搜索实际展开的不同前沿状态数为S，每状态复制、排序与类型转移在O(n log n)以内，记忆化未受限时O(Sn log n)时间；状态数最坏指数级，不能声称多项式算法。实现将缓存限制为32000项且键字节合计不足8MB，超出后不缓存但继续精确搜索；递归与临时森林保守O(n²)空间。n≤300，完整规模星、链、二叉与随机树均另用独立整数优化模型核验。

易错点

每周期只能切一条边，不能把它误写成每个感染者各切一边，也不能用“每层保护最大子树”当成总是正确的贪心。相同深度的不同感染分支共享本周期唯一切断机会。初始患者始终计入，n=1时答案为1。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> child;
vector<int> sz;
unordered_map<string, int> memo;
size_t cachedBytes = 0;
string key(const vector<int> &v) {
    string s;
    for (int x : v) {
        s.push_back(char(x & 255));
        s.push_back(char((x >> 8) & 255));
    }
    return s;
}
int solve(vector<int> front) {
    if (front.size() <= 1)
        return 0;
    sort(front.begin(), front.end());
    string k = key(front);
    auto got = memo.find(k);
    if (got != memo.end())
        return got->second;
    vector<int> all;
    for (int x : front)
        all.insert(all.end(), child[x].begin(), child[x].end());
    sort(all.begin(), all.end());
    vector<int> choices = front;
    sort(choices.begin(), choices.end(), [](int a, int b) {
        return sz[a] != sz[b] ? sz[a] > sz[b] : a < b;
    });
    choices.erase(unique(choices.begin(), choices.end()), choices.end());
    int lower = (int)front.size() - 1, best = INT_MAX;
    for (int x : choices) {
        vector<int> sub = child[x], next;
        sort(sub.begin(), sub.end());
        set_difference(all.begin(), all.end(), sub.begin(), sub.end(), back_inserter(next));
        if (lower + max(0, (int)next.size() - 1) >= best)
            continue;
        best = min(best, lower + solve(move(next)));
        if (best == lower)
            break;
    }
    if (memo.size() < 32000 && cachedBytes + k.size() < 8000000) {
        cachedBytes += k.size();
        memo.emplace(move(k), best);
    }
    return best;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m))
        return 0;
    vector<vector<int>> g(n);
    for (int i = 0, u, v; i < m; i++) {
        cin >> u >> v;
        --u;
        --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int> par(n, -1), order(1, 0), type(n);
    for (size_t i = 0; i < order.size(); i++) {
        int u = order[i];
        for (int v : g[u])
            if (v != par[u]) {
                par[v] = u;
                order.push_back(v);
            }
    }
    map<vector<int>, int> ids;
    for (int i = n - 1; i >= 0; i--) {
        int u = order[i];
        vector<int> v;
        int size = 1;
        for (int w : g[u])
            if (par[w] == u) {
                v.push_back(type[w]);
                size += sz[type[w]];
            }
        sort(v.begin(), v.end());
        auto it = ids.find(v);
        if (it == ids.end()) {
            int id = child.size();
            child.push_back(v);
            sz.push_back(size);
            ids[v] = id;
            type[u] = id;
        } else
            type[u] = it->second;
    }
    memo.reserve(32000);
    cout << 1 + solve(child[type[0]]) << '\n';
}