E2. Escape The Maze (hard version) - 题解

比赛与标签

比赛: Codeforces Round 756 (Div. 3) 标签: dfs and similar, dp, greedy, shortest paths, trees 难度: *1900

题目大意喵~

在一个由 n 个房间和 n-1 条走廊组成的树形迷宫里，上演着一场追逐战！

玩家 Vlad酱: 从 1 号房间出发，目标是到达任意一个非1号的叶子节点（也就是只连接一条走廊的房间）来获得胜利。
k 个朋友: 分散在迷宫的不同房间里，他们的目标是在 Vlad酱成功逃脱前，在某个房间或走廊上与他相遇。

所有参与者（Vlad酱和朋友们）移动速度相同，每单位时间可以移动一条走廊。

我们的任务是，判断朋友们能否保证抓住 Vlad酱。如果 Vlad酱无论如何都能逃脱，我们就输出 -1。否则，我们需要计算出，最少需要留下多少个朋友，就能保证一定能抓住 Vlad酱。

简单来说，就是求一个最小的朋友子集，使得 Vlad酱必败无疑，然后输出这个子集的大小。如果不存在这样的子集，就输出 -1 呐。

解题思路大作战！

这道题的核心是比较 Vlad酱和朋友们到达同一个房间的时间，是一场彻头彻尾的速度竞赛呢！我们可以分三步来解决这个问题，喵~

第一步：计算朋友们的“势力范围”

首先，我们得知道朋友们最快能到达每个房间的时间。如果让他们各自为战，分析起来太复杂啦。所以，我们可以把所有朋友看作一个整体。他们最快到达房间 u 的时间，就是所有朋友中到达 u 的最短时间。

这不就是一个经典的多源最短路问题嘛！我们可以用一次 多源BFS 来解决。

创建一个队列，把所有朋友的起始位置都放进去。
创建一个距离数组 dist_friend，初始化朋友们所在位置的距离为 0，其他为无穷大。
进行 BFS 遍历，计算出每个房间 u 离最近的朋友的距离 dist_friend[u]。

这样，我们就有了朋友们对整个地图的控制力地图啦！

第二步：判断 Vlad酱能否逃脱（全力围堵模式）

在计算最少朋友数量之前，我们得先确定朋友们到底能不能赢。当然是假设所有朋友都参与围堵啦！

Vlad酱要想安全地从房间 p 移动到相邻的房间 u，他到达 u 的时间必须 严格小于 任何一个朋友到达 u 的时间。也就是说，如果 Vlad酱到达 p 花了 t 时间，那么他到达 u 的时间是 t+1。这个移动是安全的，当且仅当 t + 1 < dist_friend[u]。如果 t + 1 >= dist_friend[u]，就意味着朋友可以同时或更早到达 u，Vlad酱就被抓住了！

我们可以用一次从 1 号点开始的 BFS 来模拟 Vlad酱的逃跑过程：

创建一个队列，放入起点 1。
记录 Vlad酱到达每个点的时间 dist_vlad。
在 BFS 过程中，只有当满足 dist_vlad[p] + 1 < dist_friend[u] 时，Vlad酱才能从 p 前往 u。
如果在这次 BFS 中，Vlad酱能够到达任何一个叶子节点，那就说明即使所有朋友都在，也抓不住他。这种情况下，答案就是 -1。

第三步：计算最少需要的朋友数量

如果上一步的结论是 Vlad酱无法逃脱，那我们就要计算最少需要多少朋友了。这部分是这道题的精髓所在，需要一点点贪心的思想，喵~

我们可以把这个问题想象成：Vlad酱在前面跑，我们需要在关键路口设置路障（朋友）来堵住他。需要多少个路障呢？

我们可以再进行一次从 1 号点开始的遍历（用 DFS 或 BFS 都可以，代码里用的是 BFS）。这次遍历的目的不是看能不能逃，而是计算需要多少“防守力量”。

想象一下 Vlad酱在树上向下探索：

当 Vlad酱从父节点 p 准备进入子节点 u 时，如果他会被抓住（即 dist_vlad[p] + 1 >= dist_friend[u]），那么整个以 u 为根的子树都被朋友们封锁了。我们只需要一个朋友就能完成这个封锁任务（具体是哪个朋友不重要，只要能及时赶到 u 就行）。所以，我们给需要的防守力量计数器 ans 加一，并且不再继续探索这个子树。
如果 Vlad酱可以安全进入 u（即 dist_vlad[p] + 1 < dist_friend[u]），他就会继续向 u 的子树深处探索。
特殊情况：如果 Vlad酱安全到达的这个 u 节点本身就是一个叶子节点呢？呀！这是一个潜在的出口！为了堵住这个出口，我们必须在这里安排一个朋友。所以，我们同样给 ans 加一。

通过这种方式，我们从根节点开始，每当遇到一个被完全封锁的子树，或者一个可以安全到达的叶子出口时，就计数一次。这个总数，就是我们需要的最小朋友数量啦！因为每个计数都代表了一个独立的、必须被防守的区域或出口。

代码实现，Nya~

下面就是把我们的思路变成代码的时刻啦！注释里有详细的解释哦。

cpp

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// 主函数入口喵~
int main() {
    // 加速输入输出，让程序跑得更快！
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<int> friends(k);
        for (int i = 0; i < k; i++) {
            cin >> friends[i];
        }
        vector<vector<int>> adj(n + 1);
        for (int i = 0; i < n - 1; i++) {
            int u, v;
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }

        // --- 第一步：多源BFS，计算所有朋友到各点的最短距离 ---
        vector<int> df_all(n + 1, -1); // df_all[i] 表示朋友最快到达 i 的时间
        queue<int> q;
        for (int x : friends) {
            df_all[x] = 0; // 朋友们在自己的位置，时间为0
            q.push(x);
        }
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (df_all[v] == -1) { // 如果还没被访问过
                    df_all[v] = df_all[u] + 1;
                    q.push(v);
                }
            }
        }

        // --- 第二步：BFS，检查Vlad在所有朋友围堵下能否逃脱 ---
        vector<bool> vis1(n + 1, false);
        vector<int> dep1(n + 1, 0); // dep1[i] 表示Vlad到达 i 的时间
        queue<int> q1;
        bool escaped = false; // Vlad是否成功逃脱的标志
        
        vis1[1] = true;
        q1.push(1);
        while (!q1.empty()) {
            int u = q1.front(); q1.pop();
            // 如果到达了一个非起点的叶子节点，说明成功逃脱！
            if (u != 1 && adj[u].size() == 1) {
                escaped = true;
                break;
            }
            for (int v : adj[u]) {
                if (vis1[v]) continue;
                // 关键判断：Vlad到达v的时间(dep1[u]+1)必须严格小于朋友到达v的时间
                if (dep1[u] + 1 < df_all[v]) {
                    vis1[v] = true;
                    dep1[v] = dep1[u] + 1;
                    q1.push(v);
                }
            }
        }

        if (escaped) {
            cout << -1 << '\n'; // 能逃脱，输出-1
            continue;
        }

        // --- 第三步：BFS，计算最少需要的朋友数量 ---
        // 如果无法逃脱，我们来计算最少需要多少朋友来封锁
        vector<bool> vis2(n + 1, false);
        vector<int> dep2(n + 1, 0); // 同样是Vlad的移动时间
        queue<int> q2;
        int ans = 0; // 最少需要的朋友数

        vis2[1] = true;
        q2.push(1);
        while (!q2.empty()) {
            int u = q2.front(); q2.pop();
            for (int v : adj[u]) {
                if (vis2[v]) continue;
                vis2[v] = true;
                // 如果朋友能比Vlad先到或同时到v，这个子树就被封锁了
                if (df_all[v] <= dep2[u] + 1) {
                    ans++; // 需要一个朋友来防守这个入口
                } else {
                    // 如果Vlad可以安全到达v
                    // 并且v是一个叶子节点，那么这是一个逃生出口
                    if (v != 1 && adj[v].size() == 1) {
                         ans++; // 需要一个朋友来堵住这个出口
                    } else {
                        // 否则，Vlad继续深入探索
                        dep2[v] = dep2[u] + 1;
                        q2.push(v);
                    }
                }
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

复杂度分析的说

时间复杂度: O(N) 的说。整个算法的核心是三次 BFS 遍历。每次 BFS 都会访问每个节点和每条边最多一次。因为迷宫是树形结构，边数 M = N-1，所以单次 BFS 的复杂度是 O(N+M) = O(N)。总的时间复杂度就是 O(N) 啦，对于每个测试用例来说都非常高效！
空间复杂度: O(N) 的说。我们使用了邻接表 adj 来存图，以及一些大小为 N 的辅助数组（如 df_all, dep1, vis1 等）和队列。这些空间开销都和节点数 N 成正比，所以空间复杂度是 O(N)。

知识点与总结喵~

这道题真是一次有趣的思维锻炼呢！让我们来总结一下学到了什么吧：

多源BFS: 解决“到最近的某类点的距离”问题的标准武器！当有多个源点时，把它们一股脑全塞进初始队列里，就能轻松搞定。
树上博弈与最短路: 很多树上的追逐问题，本质都是在比较双方到达某个点的最短路。想清楚谁快谁慢，问题就解决了一大半。
贪心策略: 在计算最小朋友数时，我们采用了贪心思想。每当发现一个可以被整体封锁的子树，或者一个必须被堵住的出口，我们就立刻分配一个“防守名额”。这种“只在必要时行动”的策略，帮助我们找到了最优解。
问题分解: 将一个复杂问题分解成几个更简单的子问题是解题的好习惯！我们先判断“能否赢”，再计算“怎么用最小代价赢”，思路就清晰多啦！

希望这篇题解能帮助你理解这道题目！编程的世界就像一个大迷宫，充满了挑战和乐趣，只要我们一步一步耐心探索，总能找到出口的！大家要继续加油哦，喵~

E2. Escape The Maze (hard version) - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路大作战！ ​

第一步：计算朋友们的“势力范围” ​

第二步：判断 Vlad酱 能否逃脱（全力围堵模式） ​

第三步：计算最少需要的朋友数量 ​

代码实现，Nya~ ​

复杂度分析的说 ​

知识点与总结喵~ ​