Comet OJ - Contest #9 & X Round 3 核心城市（树的直径）

题目描述

X 国有 nn 座城市，n − 1n−1 条长度为 11 的道路，每条道路连接两座城市，且任意两座城市都能通过若干条道路相互到达，显然，城市和道路形成了一棵树。

X 国国王决定将 kk 座城市钦定为 X 国的核心城市，这 kk 座城市需满足以下两个条件：

1. 这 kk 座城市可以通过道路，在不经过其他城市的情况下两两相互到达。
2. 定义某个非核心城市与这 kk 座核心城市的距离为，这座城市与 kk 座核心城市的距离的最小值。那么所有非核心城市中，与核心城市的距离最大的城市，其与核心城市的距离最小。你需要求出这个最小值。

输入描述

第一行 22 个正整数 n,kn,k。

接下来 n - 1n−1 行，每行 22 个正整数 u,vu,v，表示第 uu 座城市与第 vv 座城市之间有一条长度为 11 的道路。

数据范围：

• 1 \le k < n \le 10 ^ 51≤k<n≤105。
• 1 \le u,v \le n, u \ne v1≤u,v≤n,u=v，保证城市与道路形成一棵树。

输出描述

一行一个整数，表示答案。

样例输入 1 

6 3 1 2 2 3 2 4 1 5 5 6

样例输出 1

1

提示

【样例说明】

钦定 1,2,5 这 3 座城市为核心城市，这样 3,4,6另外 33 座非核心城市与核心城市的距离均为 1，因此答案为 1。

题意就是选取k个城市，这k个城市必须是在一堆的，因为题意要求不经过其他非核心城市可以走到任意核心城市

这道题，我一开始的思路是先找到根节点，然后再找最大深度，但是这种思路是不全面的，我们把核心城市放到一块，由边缘向中心扩散，找够非核心城市，这个深度就是最小距离，边缘就是叶子节点。

AC代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include<queue>
#include<set>
#include<iomanip>
#include<math.h>
#include<vector>
#include<map>
using namespace std;
typedef long long ll;
typedef double ld;
const int INF = 0x3f3f3f3f;
const int N = 1e5 + 5;
int n, k, degree[N], deep[N];
vector<int> v[N];
queue<int> q;
int main()
{
    scanf("%d %d", &n, &k);
    for (int i=1; i<n; i++)
    {
        int a, b;
        scanf("%d %d", &a,&b);
        v[a].push_back(b);
        v[b].push_back(a);
        degree[a]++;
        degree[b]++;
    }
    for(int i=1; i<=n; i++)
    {
        if(degree[i]==1)
        {
            q.push(i);
            deep[i]=1;
        }
    }
    int x, y, cnt=n-k;
    while(q.size())
    {
        cnt--;
        x=q.front();
        q.pop();
        if(!cnt)
        {
            printf("%d\n",deep[x]);
            break;
        }
        for(int i=0; i<v[x].size(); i++)
        {
            y=v[x][i];
            degree[y]--;
            if(degree[y]==1)
            {
                deep[y]=deep[x]+1;
                q.push(y);
            }
        }
    }
    return 0;
}