解题思路

二分半径 $r$。同时剥去 $r$ 轮叶子，余树记为 $C$。若 $|C|\le k$，直接可行；否则，可将选点投影至 $C$ 而不影响可行性。

核心叶子的最大悬挂深度为 $r$，故必须选取。漏选分叉点或留下两段缺口都会产生至少三个连通块，因此，只需在一条度为 $2$ 的链上删去连续 $D=|C|-k$ 个点。

将链编号为 $0,\dots,s$，两端保留。设 $h_i$ 为点 $i$ 的悬挂部分最大深度，$b_i=r-h_i$。删除 $L+1,\dots,L+D$ 后，点 $i$ 的悬挂部分无法被覆盖的条件为：

$$\min(i-L,L+D+1-i)>b_i\iff i+b_i-D\le L<i-b_i$$

用差分维护这些禁用区间。扫描到 $i$ 时检查 $L=i-D\ge0$：后续点 $j>i$ 的区间左端点至少为 $j-D>L$，不会影响当前候选。若覆盖计数为 $0$，则找到合法缺口。$D>2r$ 时无解。

预处理各点邻居剥叶时间的前三大值 $t_1\ge t_2\ge t_3$，不足补 $0$。该点为链内点的条件及其悬挂高度为：

$$t_2>r\ge t_3,h_i=t_3$$

沿前两大值对应的邻点扫描各链，每次判定 $O(n)$，总时间复杂度 $O(n\log n)$。

参考代码

1.55 KBcpp

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

const int N=1000005;
vector<int> G[N];
int tim[N],deg[N],q[N],f[N],a[N],b[N],c[N],h[N];
bool mid[N];
bool check(int r,int n,int k)
{
	int len=deg[r+1]-k;
	if(len<=0)return 1;
	if(len>2*r)return 0;
	for(int i=1;i<=n;i++)mid[i]=h[i]>r&&c[i]<=r;
	for(int i=1;i<=n;i++)
	{
		if(!mid[i]||(mid[a[i]]&&mid[b[i]]))continue;
		int u=i,v=mid[a[i]]?b[i]:a[i],cur=0,j=0;
		f[0]=0;
		while(mid[u])
		{
			mid[u]=0;
			j++;
			f[j]=0;
			int d=r-c[u],l=max(0,j+d-len),p=j-d;
			if(l<p){f[l]++;f[p]--;}
			if(j>=len)
			{
				cur+=f[j-len];
				if(!cur)return 1;
			}
			int nxt=a[u]^b[u]^v;
			v=u;
			u=nxt;
		}
	}
	return 0;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int id,T;
	cin>>id>>T;
	while(T--)
	{
		int n,k;
		cin>>n>>k;
		for(int i=1;i<=n;i++)G[i].clear();
		for(int i=1;i<n;i++)
		{
			int u,v;
			cin>>u>>v;
			G[u].push_back(v);
			G[v].push_back(u);
		}
		int l=0,r=0;
		for(int i=1;i<=n;i++)
		{
			deg[i]=G[i].size();
			tim[i]=0;
			if(deg[i]==1){tim[i]=1;q[r++]=i;}
		}
		while(l<r)
		{
			int u=q[l++];
			for(auto v:G[u])
			{
				deg[v]--;
				if(deg[v]==1){tim[v]=tim[u]+1;q[r++]=v;}
			}
		}
		fill(deg,deg+n+2,0);
		for(int i=1;i<=n;i++)
		{
			deg[tim[i]]++;
			a[i]=b[i]=c[i]=0;
			for(auto v:G[i])
			{
				if(tim[v]>tim[a[i]])swap(v,a[i]);
				if(tim[v]>tim[b[i]])swap(v,b[i]);
				c[i]=max(c[i],tim[v]);
			}
			h[i]=tim[b[i]];
		}
		for(int i=n;i>=0;i--)deg[i]+=deg[i+1];
		l=0;
		r=n;
		while(l<r)
		{
			int mid=l+r>>1;
			if(check(mid,n,k))r=mid;
			else l=mid+1;
		}
		cout<<l<<'\n';
	}
	return 0;
}