列公子

## 2. 数据结构
1. 树采用**邻接表**存储, 即 ```vector<int> Adj[maxn]```, 使用邻接矩阵 超时 18 %
2. 用一个类似邻接表的结构, 存储树中每一层有哪些节点 (存储其编号), 即 ```vec<int> depths```
3. 布尔型数组 ```bool isRemoved[maxn]``` 标记对应编号的节点**是否已被摘除**。

## 3. 算法
1. ```initDepths```用来初始化 ```depths```, 即递归地求每个节点的深度。
2. ```changeState``` 用来**摘除节点**(及其子节点) 或 **恢复节点**(及其子节点), 通过递归地操作 ```isRemoved``` 数组实现, 同时统计该子树的节点总数。
3. ```dfs``` 深度优先地搜索 树的每一层

## 4. 完整代码 (AC)
```cpp
//
// 蓝桥杯题库 1495 传染病控制
// 在树的每一层摘除一条边, 使得在摘除后的树中, 结点数最小; 亦即摘除的结点数最大
// 使用 DFS, 不能贪心
//
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 310;
int N, P;      // 结点数. 边数

bool isRemoved[maxn];      // 各个结点是否被剪掉了
vector<int> G[maxn];      // 邻接表
vector<int> depths[maxn];    // 每一层有哪些编号的结点  depth[2] 为树的第二层有哪些结点

void initDepths(int layer, int node){       // 初始化 depths
    depths[layer].push_back(node);

for (int v = 0; v < G[node].size(); v ++){
        int cur = G[node][v];
        initDepths(layer + 1, cur);
    }
}

int changeState(int num, bool state){       // 将编号为 num 的所有子节点 的 isRemoved 置为 state
    int sum = 1;        // 处理的所有结点数, 可能是剪去/加上
    isRemoved[num] = state;

for (int i = 0; i < G[num].size(); i++)
        sum += changeState(G[num][i], state);
    return sum;
}

int ans = 0;    // 从树中摘除的结点数 最大值

void dfs(int layer, int tot){
    ans = max(ans, tot);
    // 逐个遍历该层节点
    for (int v = 0; v < depths[layer].size(); v++){
        int cur = depths[layer][v];

if (!isRemoved[cur]) {
            int val = changeState(cur, true);  // 摘去的节点数
            dfs(layer + 1, tot + val);
            changeState(cur, false);        // 回溯
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(isRemoved, 0, sizeof(isRemoved));

cin >> N >> P;
    for (int i = 0; i < P; i++){
        int a, b;
        cin >> a >> b;
        if (a > b)
            swap(a, b);
        G[a].push_back(b);
    }

initDepths(1, 1);
    dfs(2, 0);

cout << N - ans << "\n";        // 计算剩余的节点数
    return 0;
}
```
## 5. 为什么不能用贪心
考虑这样的一颗树：
![不能用贪心的树](/image_editor_upload/20200213032139_99083.jpg "不能用贪心的树")
## 6. 参考的解答
参考了以下解答, 在此表示感谢。
[解答1](https://blog.csdn.net/zvenWang/article/details/87970374)
[解答2](https://blog.csdn.net/Eric1561759334/article/details/82502078)

0.0分

5 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

flags

这组数据似乎通不过啊7 6 1 6 1 7 6 2 6 3 7 4 7 5

2021-03-11 14:21:34

Emilia

简单易懂的回溯，可以的

2020-11-25 15:17:07

一起闹〆朱瑞晗

牛逼

2020-05-09 21:55:17

陈子昂

代码太棒了！！！

2020-05-06 21:59:57

JakeLin

理解了，很棒！！！

2020-02-13 17:32:25

列公子

TA的其他文章

你可能喜欢

蛇行矩阵（C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C++代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

[1495] 传染病控制 ( C++ 语言, DFS 方法 )

评论区

精彩推荐

【出圈】（C++代码）（典型的约瑟夫环——链表解决）

逆反的01串（C++代码）（依旧推荐switch）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

【偶数求和】（C++代码）

C语言训练-素数问题（C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

大神老白（C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

三角形（C++代码）递推

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

列公子