正经题解｜补给安排

城池和道路可以看作图中的点和边，这些边可以双向到达。因为只有$n-1$条边，所以是无向无环图。根据题意，我们需要设置军事重镇，让其他点到军事重镇的距离最小。
显然，如果只有一个军事重镇，这个点应该在整个结构的中心。我们把无向图看作树，那么这个点就是树直径的中点。当军事重镇数量增加时，将会从这个点开始往外连接。所以可以用两次深搜的方法找到树的直径，找到直径的中点。将直径中点看作树的根，求出树上每个节点的深度和子树中能达到的最大深度。
子树能达到的最深深度-当前节点深度=当前节点离子树的叶子节点的最远距离
因为当前节点到军事重镇还有1的距离，所以最终距离还要加1。
优先选择距离远的作为军事重镇，那么从大到小排列后前$k$个节点都会被选入，答案就是第$k+1$个节点离子树叶子节点的最远距离+1 。

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

int n,k,zj,num;
int cut,head[100010],ver[200020],nexts[200020];
int deep[100010],f[100010],maxdeep[100010],ans[100010];
bool cmp(int a,int b){
	return a>b;
}
void add(int x,int y){
	ver[++cut]=y;nexts[cut]=head[x];head[x]=cut;
}
//求直径
void dfs1(int x,int fa){
	if(deep[x]>zj){
		zj=deep[x];
		num=x;
	}
	for(int i=head[x];i;i=nexts[i]){
		int y=ver[i];
		if(y==fa)continue;
		deep[y]=deep[x]+1;
		dfs1(y,x);
	}
}
void dfs2(int x,int fa){
	if(deep[x]>zj){
		zj=deep[x];
		num=x;
	}
	for(int i=head[x];i;i=nexts[i]){
		int y=ver[i];
		if(y==fa)continue;
		deep[y]=deep[x]+1;
		f[y]=x;
		dfs2(y,x);
	}
}
//
void dfs_k(int x,int fa){
	maxdeep[x]=deep[x];
	for(int i=head[x];i;i=nexts[i]){
		int y=ver[i];
		if(y==fa)continue;
		deep[y]=deep[x]+1;
		dfs_k(y,x);
		maxdeep[x]=max(maxdeep[x],maxdeep[y]);
	}
}
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<n;++i){
    	int x,y;
    	scanf("%d%d",&x,&y);
    	add(x,y);
    	add(y,x);
	}
    //直径
	dfs1(1,0);
	memset(deep,0,sizeof(deep));
	zj=0;
	dfs2(num,0);
    
	int kkk=num;
    //找直径的中点
	for(int i=1;i<=(deep[num]+1)/2;++i)kkk=f[kkk];
	memset(deep,0,sizeof(deep));
    //将直径中点当做根 再搜一次
    //记录每个点的深度和子树能到达的最深深度 
	dfs_k(kkk,0);
	for(int i=1;i<=n;++i)ans[i]=maxdeep[i]-deep[i];
	sort(ans+1,ans+n+1,cmp);
	printf("%d\n",ans[k+1]+1);//普通城市距离重镇还有1的距离 
    return 0;
}

另一种思路是逆向思维，选$k$个军事重镇就相当于选$n-k$个普通城市。我们把选完的普通城市看作删去，那么每一次选择的普通城市都是叶子节点，只有一条边连接。所以每次都删除入度为1的节点，并把相连节点的入度$-1$。类似于拓扑排序的写法，用两个队列存储，每轮删除离叶子节点距离相同的点，不断向中心前进。当剩余节点为$k$时，此时离叶子节点的距离即为答案。

while(sum > 0) {
	ans ++;//剩下的是军事重镇，每一轮删除，相当于叶子到军事重镇的距离+1
	while (!q1.empty()) {
		int x = q1.front();
		q1.pop();
		sum --;
		if (sum ==  k) {
			cout<<ans<<endl;
			return 0;
		}
		for (int i = head[x]; i != -1; i = edge[i].nxt) {
			int y = edge[i].v;
			du[y] --;
			if (du[y] == 1) q2.push(y);
		}
	}
	swap(q1, q2);
    //队列q1中存储离叶子节点距离相同的一批入度为1的节点
    //删除q1中节点时将相连的入度为1的点加入队列q2,作为下一批准备删除的普通城市
}