E. Gardener and Tree - 题解

比赛与标签

比赛: Codeforces Round 748 (Div. 3) 标签: brute force, data structures, dfs and similar, greedy, implementation, trees, *1600 难度: *1600

题目大意喵~

一位勤劳的园丁 Vitaly 种了一棵有 n 个节点的树，他想给这棵树修剪一下~ 他的修剪方式很特别：每一次操作，他会同时把树上所有的叶子节点都剪掉。一个叶子节点是指度数小于等于1的节点哦（也就是说，它最多只连接一个其它节点）。

Vitaly 会连续进行 k 次这样的修剪操作。我们的任务就是，算出 k 次操作之后，树上还剩下多少个节点呢？

举个栗子，如果一棵树有两个节点，它们互相连接。那么它们俩都是叶子，一次操作后就都被剪掉啦，剩下0个节点。是不是很有趣的说？

解题思路呐

喵哈喽~ 小伙伴们！这个问题看起来就像是在一层一层地剥洋葱，或者说是在剥一棵神奇的树皮！每剪一次，我们就剥掉最外面的一层。这样想的话，思路是不是就清晰多啦？

这个“一层一层”的特性，立马让聪明的猫娘我想到了 广度优先搜索（BFS）！BFS 最擅长处理这种分层遍历的问题了。

我们可以把这个修剪过程想象成一个从外向内的“侵蚀”过程：

第1层: 最初始的叶子节点，它们是第一批被剪掉的。
第2层: 当第1层的叶子被剪掉后，一些原本不是叶子的节点，因为邻居被剪掉了，它们的度数减小，也变成了叶子。这些新晋的叶子就是第二批被剪掉的。
第 i 层: 在第 i-1 次修剪后，新产生的叶子节点，它们会在第 i 次操作中被剪掉。

所以，我们可以给每个节点定义一个“层数”，layer[i] 表示节点 i 是在第几次操作中被剪掉的。

那么解题步骤就出来啦：

建图和初始化: 我们需要用邻接表来存这棵树，并且用一个 deg 数组来记录每个节点的初始度数。再来一个 layer 数组，初始化为0，用来记录每个节点的“层数”。
找到第一层叶子: 遍历所有节点，把所有度数小于等于1的节点找出来。它们就是我们的“第1层”叶子。我们把它们放进一个队列里，准备开始BFS，并把它们的 layer 值标记为1。
BFS模拟修剪过程:
- 从队列里取出一个节点 u（代表它被“剪掉”了）。
- 遍历 u 的所有邻居 v。
- 因为 u 被剪掉了，所以 v 的度数要减1。
- 这时，我们检查一下邻居 v：如果 v 的 layer 还是0（说明它还没被分配到任何层），并且它的度数减1后也变成了1（说明它成了新的叶子），那么它就属于下一层！
- 我们把 v 的层数设为 layer[u] + 1，然后把它也加入队列。
统计结果: 当BFS结束后，layer 数组就记录了每个节点会在第几轮被剪掉。题目问的是经过 k 轮操作后还剩多少节点。那不就是所有 layer 值大于 k 的节点嘛！我们只需要遍历一遍 layer 数组，数一数有多少个节点的 layer > k 就好啦！

这个方法是不是很直观呢？通过一次BFS，我们就模拟了整个修剪过程，并得到了每个节点的“生存时间”，问题就迎刃而解了喵~

代码实现喵~

cpp

#include <iostream>
#include <vector>
#include <queue>
#include <sstream>
#include <string>

using namespace std;

int main() {
    // 喵~ 为了快一点，关掉同步流！
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    string dummy;
    // 有时候测试用例之间有空行，先读掉它
    getline(cin, dummy); 

    for (int test = 0; test < t; test++) {
        string line;
        // 这个循环是为了处理测试用例之间可能存在的多个空行
        while (getline(cin, line)) {
            if (!line.empty()) break;
        }
        if (line.empty()) break; // 如果读到文件尾的空行，就结束

        stringstream ss(line);
        int n, k;
        ss >> n >> k; // 从非空行中读取 n 和 k

        // 使用邻接表来存图，deg数组记录每个节点的度
        vector<vector<int>> graph(n + 1);
        vector<int> deg(n + 1, 0);
        // layer[i] 表示节点 i 在第几轮被删除
        vector<int> layer(n + 1, 0);

        for (int i = 0; i < n - 1; i++) {
            int u, v;
            cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
            deg[u]++;
            deg[v]++;
        }

        // BFS的队列，用于分层处理
        queue<int> q;
        // 找到所有初始的叶子节点（第1层）
        for (int i = 1; i <= n; i++) {
            if (deg[i] <= 1) {
                q.push(i);
                layer[i] = 1; // 标记为第1层
            }
        }

        // 开始BFS，模拟剪枝过程
        while (!q.empty()) {
            int u = q.front();
            q.pop();

            // 遍历当前被“剪掉”的节点的邻居
            for (int v : graph[u]) {
                deg[v]--; // 邻居的度数减1
                // 如果邻居还没被分层，并且它现在也变成了叶子
                if (layer[v] == 0 && deg[v] <= 1) {
                    layer[v] = layer[u] + 1; // 它的层数是当前节点的层数+1
                    q.push(v); // 加入队列，等待下一轮处理
                }
            }
        }

        // 统计 k 轮后还剩下的节点数
        int count = 0;
        for (int i = 1; i <= n; i++) {
            // 如果一个节点的删除层数大于 k，说明它在 k 轮后还活着
            if (layer[i] > k) {
                count++;
            }
        }
        cout << count << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度: O(N) 的说。在每个测试用例中，我们首先需要 O(N) 的时间来建图和计算初始度数。然后，BFS的过程中，每个节点和每条边都只会被访问一次。因为这是一棵树，边数 M = N-1。所以BFS的时间复杂度是 O(N+M) = O(N)。最后统计答案也是 O(N)。总的来说，每个测试用例的处理时间是 O(N) 呐。
空间复杂度: O(N) 的说。我们使用了邻接表 graph 来存图，它占用的空间是 O(N+M) = O(N)。deg 数组、layer 数组和BFS用的队列 q 都需要 O(N) 的空间。所以总的空间复杂度是 O(N) 喵~

知识点与总结

这道题真是太棒了，可以让我们加深对图论算法的理解！

核心算法: 广度优先搜索 (BFS) 的巧妙应用。这道题告诉我们，BFS 不仅仅能求最短路，它更是解决所有“分层”问题的利器！当你发现一个问题可以一层一层地解决时，一定要想想BFS哦！
拓扑排序思想: 这个解法和拓扑排序的思想非常相似。拓扑排序是不断移除入度为0的节点，而我们这里是不断移除度数为1的节点。两者都是从图的“边缘”开始，逐步向内处理。
数据结构: 邻接表 + 度数数组 + 队列 是处理这类图论问题的经典组合，一定要熟练掌握呀！
问题转化: 最重要的一步是将“进行k次操作”这个问题，转化为“计算每个节点在哪一层被移除”。一旦完成了这个转化，问题就变得非常清晰了。

希望这篇题解能帮助到你！只要多思考，多练习，再难的题目也都能被我们攻克的说！加油喵~ >w<

E. Gardener and Tree - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路呐 ​

代码实现喵~ ​

复杂度分析 ​

知识点与总结 ​