F. Minimum Maximum Distance - 题解

比赛与标签

比赛: Codeforces Round 903 (Div. 3) 标签: dfs and similar, dp, graphs, shortest paths, trees 难度: *1700

喵喵的题目解析~

哈喽，各位小伙伴们，今天我们来攻略一道非常有趣的树上问题，喵~

题目是这样描述的：我们有一棵可可爱爱的树，树上有 n 个节点，其中有 k 个节点被特别“标记”了出来。对于树上的任何一个节点 i，我们需要计算一个值 f(i)。这个 f(i) 是什么呢？它呀，是节点 i 到 所有 被标记的节点中，最远的那一个的距离，的说。

我们的任务，就是在这棵树上找到一个“最佳碰头地点”，让这个“最远距离”尽可能地小。也就是说，我们要计算出所有 f(i)（从 f(1) 到 f(n)），然后找出其中的最小值。

举个栗子🌰：想象一下，几个朋友（被标记的节点）约好在公园（一棵树）里碰面，他们想找一个集合点（某个节点 i），使得离这个集合点最远的朋友走的路程最短。我们要找的就是这个“最短的最远路程”是多少，呐。

寻找最佳集合点的旅程喵~

这道题的核心是 min(max(dist))，也就是最小化最大值问题。一看到这个，很多同学可能会想到二分答案，对吧？但其实，这道题有一个更优雅、更直观的解法哦，喵~

让我们来深入思考一下问题的本质。我们要找一个节点 c，使得 max_{m 是标记点} dist(c, m) 最小。

想象一下，在所有被标记的节点中，肯定有两个节点，它们之间的距离是所有被标记节点对中最远的。我们把这条最长的路径称为“标记节点集的直径”，它的两个端点我们叫 a 和 b，长度为 D。

现在，对于我们想找的任何一个最佳碰头点 c，它到 a 和 b 的距离之和至少是 D（根据树上路径的唯一性和三角不等式，dist(a, b) <= dist(a, c) + dist(c, b)）。这意味着 max(dist(c, a), dist(c, b)) 必然大于等于 D / 2。所以，我们要求的答案，也就是 min(f(i))，最小也得是 ceil(D / 2)。

那我们能不能真的找到一个点，让它的最远距离恰好就是 ceil(D / 2) 呢？当然可以啦！这个神奇的点就在直径 a-b 的路径上！我们只要取这条路径的“中点” c 就行了。

1. 为什么是中点？

   • 这个中点 c 到 a 和 b 的距离最大就是 ceil(D / 2)。
   • 那么，c 到任何其他标记点 m 的距离会超过这个值吗？答案是不会的，喵~ 如果真的存在一个标记点 m，使得 dist(c, m) > ceil(D / 2)，那么通过一些简单的推导（利用三角不等式），我们就能发现 m 和 a 或 b 之间的距离会超过 D，这就和我们之前定义的“D 是直径”相矛盾了。所以假设不成立！

2. 问题的转化 所以，这道题就奇妙地转化成了一个更简单的问题：求出这 k 个标记节点所构成的“子图”的直径 D，最终答案就是 (D + 1) / 2（这里用整数除法的小技巧来计算 ceil(D / 2))。

3. 如何求标记节点集的直径？ 这可是个经典算法哦，只需要两遍 BFS (广度优先搜索) 就能搞定：

   • 第一步: 随便从一个标记点（比如第一个 marks[0]）出发，做一次 BFS，找到离它最远的一个标记点 a。
   • 第二步: 从点 a 出发，再做一次 BFS，找到离 a 最远的一个标记点 b。
   • a 和 b 之间的距离 dist(a, b) 就是我们想要的直径 D 啦！

这个方法是不是既简单又高效呢？喵~

代码实现魔法，变身喵~

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

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

using namespace std;

int main() {
    // 加速输入输出，让程序跑得飞快，喵~
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;

        // 记录所有被标记的节点
        vector<int> marks(k);
        for (int i = 0; i < k; i++) {
            cin >> marks[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);
        }

        // 用一个布尔数组快速判断一个点是否被标记
        vector<bool> marked(n + 1, false);
        for (int i = 0; i < k; i++) {
            marked[marks[i]] = true;
        }

        // --- 第一遍 BFS ---
        // 目标：从任意一个标记点出发，找到离它最远的标记点
        vector<int> dist1(n + 1, -1); // dist1[i] 存储从起点到 i 的距离
        queue<int> q;

        // 我们就从第一个标记点 marks[0] 开始吧
        dist1[marks[0]] = 0;
        q.push(marks[0]);

        while (!q.empty()) {
            int u = q.front();
            q.pop();

            for (int v : adj[u]) {
                if (dist1[v] == -1) { // 如果 v 还没被访问过
                    dist1[v] = dist1[u] + 1;
                    q.push(v);
                }
            }
        }

        // 找到距离 marks[0] 最远的标记点，它将是直径的一个端点
        int farthest = marks[0];
        for (int i = 1; i <= n; i++) {
            if (marked[i] && dist1[i] > dist1[farthest]) {
                farthest = i;
            }
        }

        // --- 第二遍 BFS ---
        // 目标：从刚才找到的端点 farthest 出发，找到离它最远的标记点，计算直径
        vector<int> dist2(n + 1, -1);
        dist2[farthest] = 0;
        q.push(farthest);

        while (!q.empty()) {
            int x = q.front();
            q.pop();

            for (int v : adj[x]) {
                if (dist2[v] == -1) {
                    dist2[v] = dist2[x] + 1;
                    q.push(v);
                }
            }
        }

        // 在所有标记点中，找到离 farthest 最远的距离，这就是直径
        int diameter = 0;
        for (int i = 1; i <= n; i++) {
            if (marked[i] && dist2[i] > diameter) {
                diameter = dist2[i];
            }
        }

        // 最终答案就是直径的一半（向上取整）
        cout << (diameter + 1) / 2 << '\n';
    }
    return 0;
}

时间与空间的舞蹈喵

• 时间复杂度: O(N + K) 的说。 我们对整棵树进行了两次完整的 BFS，每次 BFS 的复杂度是 O(N)，因为要访问所有节点和边。中间查找最远点的过程需要遍历 k 个标记点，是 O(K)。所以每个测试用例的总时间复杂度是 O(N + K)。因为 K <= N，也可以简单地说是 O(N) 啦。
• 空间复杂度: O(N) 的说。 我们主要使用了邻接表 adj、距离数组 dist1 和 dist2、标记数组 marked 以及 BFS 用的队列 q。它们都需要 O(N) 的空间来存储。

猫娘的小鱼干仓库

这道题真是太棒了，它教会了我们：

1. 问题转化: 很多看起来复杂的 min(max) 问题，背后可能隐藏着一个漂亮的几何或图论性质。将问题转化为求“标记点集的直径”是解题的关键一步，喵~
2. 树的直径: 求解树（或树上一个点集）的直径，"两遍BFS/DFS"法是一个非常标准且高效的模板，一定要记在小本本上呐！
3. BFS的应用: BFS 是求解无权图中单源最短路径的不二之选。在这道题里，它被完美地用来计算节点间的距离。
4. 向上取整: (a + b - 1) / b 是计算 ceil(a/b) 的常用整数运算技巧。对于除以2的情况，(a + 1) / 2 就足够了。

希望这篇题解能帮助到大家！只要我们勤于思考，再难的题目也能像解开毛线团一样迎刃而解的！加油哦，喵~！