思路
因为所有核心城市两两可互相到达，不妨将所有核心城市缩成一个点，然后考虑这个点会在图上的什么地方出现。题目要求使其他点到这个点距离的最大值最小，不难想到树的直径，该点是直径中点。
然后再把核心城市放回去，考虑怎么选择这 \(k\) 个点。依然按照上述思路，找最小。首先仍是直径中点，然后贪心地选剩下的点。处理出每个点离直径中点的距离和能该点到能到达的离直径中点最远的点的距离，每次找最大值选入核心城市，保证每次减少距离最远的点的距离。最后的答案便是剩下的最大的点。
实现
找直径中点，预处理直径端点到每个点的距离，从另一端点搜到距离正好是该端点一半的点即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,k;
int h[N],tot;
int dv1,dv2,dmax;
int dep[N],maxd[N],fa[N],w[N];
struct Node{int to,nxt;
}e[2*N];
void Add(int u,int v){tot++;e[tot].to=v;e[tot].nxt=h[u];h[u]=tot;
}
void dfs(int u,int cur,int fath){dep[u]=cur;fa[u]=fath;maxd[u]=dep[u];if(dmax<cur) dmax=cur,dv1=u;for(int i=h[u];i;i=e[i].nxt){int v=e[i].to;if(v==fath) continue;dfs(v,cur+1,u);maxd[u]=max(maxd[u],maxd[v]);}
}
bool cmp(int x,int y){return x>y;
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>k;for(int i=1;i<=n-1;i++){int u,v;cin>>u>>v;Add(u,v),Add(v,u);}dfs(1,0,0);dv2=dv1,dmax=dv1=0;memset(dep,0,sizeof(dep));dfs(dv2,0,0);int dt=dv1;for(int i=1;i<=(dep[dv1]+1)/2;i++) dt=fa[dt];memset(dep,0,sizeof(dep));dfs(dt,0,0);for(int i=1;i<=n;i++) w[i]=maxd[i]-dep[i];sort(w+1,w+1+n,cmp);cout<<w[k+1]+1;return 0;
}