注：本题解只是优化 ZFJ 的题解。

优化了注释和 calc()，思路看注释。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
vector<int> a[N];	// 图
int dia[N],dia1,dia2;	// 直径路径和它的两个端点
int dis[N];	// 与指定点的距离
int centre;	// 树的中心
void dfs(int u,int f){
	for (int i = 0;i < a[u].size();i++){
		int v = a[u][i];
		if (v != f){
			dis[v] = dis[u] + 1;
			if (dis[v] > dis[dia1])	dia1 = v;
			dia[v] = u;
			dfs(v,u);
		}
	}
}
// 每个点到中心的距离，和每个点到它子辈中离它最远的叶结点的距离
void calc(int u,int f){
	for (int i = 0;i < a[u].size();i++){
		int v = a[u][i];
		if (v != f){
			calc(v,u);
			dis[u] = max(dis[u],dis[v] + 1);
		}
	}
}
int main(int argc, char **argv){
	int n,k;
	cin >> n >> k;
	for (int i = 1;i < n;i++){
		int u,v;
		cin >> u >> v;
		a[u].push_back(v);
		a[v].push_back(u);
	}
	// 找直径
	// 当前指定点为 dia1
	dfs(1,0);
	dia2 = dia1,dis[dia1] = 0,dia[dia1] = 0;
	dfs(dia1,0);

	// 找中心
	centre = dia1;
	int len = (dis[dia1] + 1) / 2;
	while (len--)	centre = dia[centre];

	// 每个点到中心的距离
	// 当前指定点为：以 i 为根时，它到离它最远的叶结点的距离
	memset(dis,0,sizeof dis);
	calc(centre,0);
	// printf("%d\n",centre);
	// for (int i = 1;i <= n;i++){
	// 	printf("%d ",dis[i]);
	// }

	// 这里越大的 dis[i] 越靠近中心城市，排掉 k 个中心城市就是最大的到中心城市的距离。
	// +1 就是到中心城市的距离
	sort(dis + 1,dis + n + 1);
	cout << dis[n - k] + 1;
	return 0;
}

直径解法

推荐题解1

推荐题解2

建议不要看他们的代码，码风真的一坨。看讲解扎布多德勒。

而且我对比了一下，多份代码不得不说肉眼还是能发现亿点点相似性（沉思）。

由外向内砍叶结点的做法，代码和思路都比较简洁清晰，看题解即可：

由外向内BFS砍叶子的做法题解

直径解法看我的代码（自荐）。一定要掌握！

可以帮助你深入理解直径的性质，也可以帮助你做 P1099 树网的核 这题。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

vector<int> g[N];
int d[N]; // 记录与当前轮DFS源点的距离
int r[N]; // 记录直径的路径
int A, B; // 记录直径的两个端点
int n, k;
int center; // 树的中心
int maxd[N]; // 每个结点能到达的最远的叶结点的深度
int dis[N]; // 存储 maxd[u]-d[u]，用于排序

void build() {
	int u, v;
	for (int i = 1; i < n; i++) {
		cin >> u >> v;
		g[u].emplace_back(v);
		g[v].emplace_back(u);
	}
}

// 找树的直径
// u是当前结点，f是u的父节点
void dfs(int u, int f) {
	for (auto v : g[u]) {
		if (v == f) continue;
		d[v] = d[u] + 1;
		if (d[v] > d[A]) A = v;
		r[v] = u;
		dfs(v, u);
	}
}

// 计算每个结点到中心的距离（以中心为根的结点深度）
// 同时计算每个结点能到达的最远的叶结点的深度
void calc(int u, int f) {
	maxd[u] = d[u]; // 当然也可以不记深度，而是最远的叶结点与u的距离，后面就不用减了
	for (auto v : g[u]) {
		if (v == f) continue;
		d[v] = d[u] + 1;
		calc(v, u);
		// 递归回来后统计最远叶结点深度
		maxd[u] = max(maxd[u], maxd[v]);
	}
}

int main() {
	cin >> n >> k;
	build();
	// 1. 找直径
	dfs(1, 0);
	B = A;
	d[A] = 0, r[A] = 0;
	dfs(A, 0);

	// debug
//	cout << d[A] << '\n';
//	int pre = A, len = d[A] + 1;
//	while (len--) {
//		cout << pre << ' ';
//		pre = r[pre];
//	}

	// 2. 找树的中心
	center = A;
	int len = (d[A] + 1) / 2;
	while (len--) center = r[center];
//	cout << center;

	// 3. 计算每个结点能到达的最远的叶结点的深度
	memset(d, 0, sizeof d);
	calc(center, 0);

	// 4. 计算选点依据是距离 maxd[u]-d[u]
	for (int i = 1; i <= n; i++) dis[i] = maxd[i] - d[i];
	sort(dis + 1, dis + n + 1);
	// 非核心城市与核心城市群的最大距离等于 dis[x]+1
	// （x到核心城市群还需要经过一条边）
	cout << dis[n - k] + 1;

	return 0;
}