原题链接： 核心城市

题意：给定一个 $n$ 个点的无根树，请确定一个拥有 $m$ 个点的连通块，使得图中距离连通块最远的点到连通块的距离最小。

树的直径是树上最长的路径，我们要找的 $m$个点一定包含树的直径的中点（可以把最长路径一分为二）

以任意一点为起点求距离最远的点记为 $a$，再求距离 $a$ 最远的点记为 $b$，路径 $a-b$ 就是树的直径

在 $bfs$ 求最远的点时顺便记录路径，从 $b$ 出发往回退 $\lceil \frac{dist + 1}{2} \rceil$ 步，就是直径的中点

以直径的中点为根求以每个点为根的子树中的点到自己的最远距离，记为 $d[i]$

把数组 $d$ 从大到小排序，我们把前 $m$ 个点选为我们的连通块，答案为未选入连通块的最大的 $d[i] + 1$

时间复杂度 $O(nlogn)$

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;

typedef long long LL;

const int N = 100010, M = N * 2;

int h[N], e[M], ne[M], idx;
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

int n, m;
int d[N], path[N];
int q[N];

int bfs(int root)
{
    memset(d, -1, sizeof d);
    d[root] = 0;

    int hh = 0, tt = -1;
    q[++ tt] = root;
    path[root] = -1;

    int res = root;
    while(hh <= tt)
    {
        int u = q[hh ++];

        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if(d[j] == -1)
            {
                d[j] = d[u] + 1;
                q[++ tt] = j;
                path[j] = u;

                res = j;
            }
        }
    }
    return res;
}

void dfs(int u, int fa)
{
    d[u] = 0;
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(j == fa)  continue;
        dfs(j, u);
        d[u] = max(d[u], d[j] + 1);
    }
}

int main()
{
    memset(h, -1, sizeof h);

    scanf("%d%d", &n, &m);
    for(int i = 1; i < n; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }

    int a = bfs(1),  b = bfs(a);

    a = b;
    for(int i = 0; i < (d[b] + 1) / 2; i ++)
        a = path[a];
    //printf("a = %d\n", a);
    dfs(a, -1);

    sort(d + 1, d + n + 1);
    reverse(d + 1, d + n + 1);

    printf("%d", d[m + 1] + 1);

    return 0;
}