meeting - 题解

标签与难度

标签: 图论, 树, 树的直径, 深度优先搜索, BFS, 经典算法难度: 1600

题目大意喵~

哈喵~ 主人！这道题是这样子的：在一个新建的城市里，有 $n$ 个有趣的地方，它们之间由 $n-1$ 条道路连接。这意味着，整个城市的交通网络其实是一棵树哦！每条路走一次都花费1秒钟。

现在，有 $k$ 个小伙伴，他们分别在 $k$ 个不同的地方。他们想找一个地方（ $n$ 个地方里的任意一个都可以）开个茶会，但是大家都很忙，希望所有人都能尽快到场。这个“尽快”指的是，最后到达的那个人所花的时间要尽可能短。

我们的任务就是，计算出这个最短的“最后到达时间”是多少，呐。

举个例子，如果小伙伴A到集合点要3秒，小伙伴B要5秒，那这次集合的时间就是5秒。我们要找一个集合点，让这个最大的时间（比如这里的5秒）变得最小，喵~

解题思路分析

这道题看起来有点复杂，但别怕，让我来帮你理清思路，喵~

问题的核心是：找到一个集会点 p，使得所有小伙伴 x_i 到 p 的距离的最大值 max(dist(x_i, p)) 最小。

从最简单的情况开始想

想象一下，如果只有两个小伙伴，分别在 A 点和 B 点。他们要在哪里见面最快呢？当然是在他们之间的路径上的某个中心点啦！他们俩相遇所需要的最短时间，就是他们之间距离 dist(A, B) 的一半，如果距离是奇数，就要向上取整个说。比如距离是5，他们一个走2步一个走3步，在中间碰头，最晚的那个花了3秒。这个时间就是 $\lceil \frac{\text{dist}(A, B)}{2} \rceil$ 。

扩展到多个小伙伴

现在有 $k$ 个小伙伴了。我们不妨也考虑一下，哪两个小伙伴离得最远呢？假设在所有的小伙伴中，A 和 B 是相距最远的一对。他们之间的路径，我们可以称之为这群小伙伴的“直径”。

这个“直径”非常关键！因为无论大家选在哪里集合，为了让 A 和 B 到达，花费的总时间至少是 dist(A, B)。而最晚到达的那个人花费的时间，至少是 $\lceil \frac{\text{dist}(A, B)}{2} \rceil$ 。

那么，我们能不能总能找到一个集合点，使得最长时间恰好就是这个值呢？答案是肯定的，喵！这个最优的集合点，一定也在这条“直径”路径上。如果我们把集合点选在 A 和 B 路径的中心点，那么对于任何其他小伙伴 C，他到这个中心点的距离，是不会超过 A 或 B 到中心点的距离的。这是一个树的美妙性质哦！

所以，问题就神奇地转化成了：找出这 $k$ 个小伙伴中，相距最远的一对，计算出他们之间的距离 D，那么最终答案就是 $\lceil D/2 \rceil$ ！

如何找到这群小伙伴的“直径”呢？

这和我们平时求一整棵树的直径的方法非常像，只需要稍作修改。我们可以用经典的 “两遍DFS” (或BFS) 算法，喵~

第一遍DFS：从 $k$ 个小伙伴中随便选一个作为起点，比如第一个小伙伴 start_node。从 start_node 开始进行深度优先搜索（DFS），找到离他最远的另一个小伙伴 A。注意，我们只关心小伙伴，所以最远的点必须是 $k$ 个小伙伴中的一个哦。
第二遍DFS：现在，我们认定 A 就是“直径”的一个端点。再从 A 出发，进行一次DFS，找到离 A 最远的另一个小伙伴 B。
计算结果：A 和 B 之间的距离，就是这群小伙伴的“直径” D。最终的答案就是 $\lceil D/2 \rceil$ 。在写代码的时候，为了避免浮点数，我们可以用整数除法 (D + 1) / 2 来计算，效果是一样的，非常方便！

总结一下我们的作战计划：

建图，并标记出哪些点上有小伙伴。
任选一个有小伙伴的点 s 出发，DFS 找到离 s 最远的小伙伴 A。
从 A 出发，DFS 找到离 A 最远的小伙伴 B，并记录下这个最长距离 D。
输出 (D + 1) / 2。

是不是感觉清晰多啦？让我们一起把这个想法变成漂亮的代码吧，喵~

代码实现

这是我根据上面的思路，精心重构的一份代码~ 注释很详细，希望能帮到你，呐！

cpp

#include <iostream>
#include <vector>
#include <algorithm>

// 使用邻接表来表示树，喵~
std::vector<int> adj[100005];
// 标记哪些节点上有小伙伴
bool is_person[100005] = {false};

// 用于DFS的结果，farthest_node是找到的最远小伙伴的编号，max_dist是到该小伙伴的距离
int farthest_node;
int max_dist;

/**
 * @brief 深度优先搜索，寻找从起点u出发能到达的最远的小伙伴
 * 
 * @param u 当前节点
 * @param p 父节点（防止往回走）
 * @param current_dist 从DFS起点到当前节点u的距离
 */
void find_farthest_person_dfs(int u, int p, int current_dist) {
    // 如果当前节点u是一个小伙伴的家，并且比我们之前找到的都远
    if (is_person[u] && current_dist > max_dist) {
        max_dist = current_dist;
        farthest_node = u;
    }

    // 遍历所有邻居，继续向下探索
    for (int v : adj[u]) {
        // 只要不是回头路，就继续前进！
        if (v != p) {
            find_farthest_person_dfs(v, u, current_dist + 1);
        }
    }
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, k;
    std::cin >> n >> k;

    // 读取 n-1 条边，构建我们的城市地图（树）
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 记录小伙伴们的位置
    int start_node = -1; // 我们需要一个起始小伙伴的位置
    for (int i = 0; i < k; ++i) {
        int person_location;
        std::cin >> person_location;
        is_person[person_location] = true;
        if (start_node == -1) {
            start_node = person_location; // 就决定是你了，第一个小伙伴！
        }
    }

    // --- 第一遍DFS ---
    // 从任意一个小伙伴 start_node 出发，找到离他最远的小伙伴 A
    max_dist = -1; // 初始化最大距离
    find_farthest_person_dfs(start_node, 0, 0);
    int endpoint_A = farthest_node;

    // --- 第二遍DFS ---
    // 从小伙伴 A 出发，找到离 A 最远的小伙伴 B，他们之间的距离就是“直径”
    max_dist = -1; // 重置最大距离
    find_farthest_person_dfs(endpoint_A, 0, 0);
    int diameter = max_dist;

    // 计算最终结果，喵~
    int min_time = (diameter + 1) / 2;
    std::cout << min_time << std::endl;

    return 0;
}

复杂度分析

时间复杂度: $O(N + K)$ 我们主要的操作是两次完整的深度优先搜索（DFS）。每次DFS都会访问树上的每个节点和每条边一次。因为这是一棵树，有 $N$ 个节点和 $N-1$ 条边，所以一次DFS的复杂度是 $O(N + (N-1)) = O(N)$ 。我们进行了两次DFS，所以这部分是 $O(N)$ 。读取输入需要 $O(N+K)$ 的时间。所以总的时间复杂度是 $O(N+K)$ ，效率非常高哦！
空间复杂度: $O(N)$ 我们用了一个邻接表 adj 来存储整棵树，它占用的空间是 $O(N)$ 。is_person 数组也占用了 $O(N)$ 的空间。DFS递归时，系统调用栈的深度在最坏情况下（树是一条链）也是 $O(N)$ 。所以总的空间复杂度是 $O(N)$ ，喵~

知识点总结

这道题是树上算法的一个非常经典的入门应用，通过解决它，主人可以掌握以下几个重要的知识点，呐：

树的直径: 这是本题的核心概念。虽然题目没有直接说，但我们通过分析，把问题转化为了求一个特殊点集的“直径”。
两遍DFS/BFS求直径: 这是求树的直径的标准算法，一定要牢牢记住哦！从任意点找到最远点，再从最远点找到新的最远点，这条路径就是直径。
问题转化能力: 算法竞赛的魅力就在于此！把一个看起来很复杂的问题（最小化最大距离）转化为一个我们熟悉的模型（求直径），是成为高手的必经之路，喵~
整数除法技巧: 在处理需要“向上取整”的除法时， (a + b - 1) / b 是计算 $\lceil a/b \rceil$ 的好方法。对于除以2的情况，(D + 1) / 2 更简洁。这可以帮助我们避免使用浮点数带来的精度问题。

希望我的题解对你有帮助！如果还有不明白的地方，随时可以再来问我哦，喵~

meeting - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

从最简单的情况开始想 ​

扩展到多个小伙伴 ​

如何找到这群小伙伴的“直径”呢？ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​