我想的是先用换根dp求出k=1时的那个点（因为连通块k中必然包含这个点），再二分答案：对于答案num，所需要的连通块大小

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;

const int N=100010;
vector<int>e[N*2];
int fmx[N],smx[N],fmxi[N],dis[N],dep[N];
int n,k;

void dfs1(int u,int fat)
{
	for(int i=0;i<e[u].size();i++)
	{
		int v=e[u][i];
		if(v==fat)continue;
		dfs1(v,u);
		if(fmx[v]+1>fmx[u])fmxi[u]=v,smx[u]=fmx[u],fmx[u]=fmx[v]+1;
		else if(fmx[v]+1>smx[u])smx[u]=fmx[v]+1;
	}
}
void dfs2(int u,int fat)
{
	int mx=(fmxi[fat]==u?smx[fat]:fmx[fat]);
	if(mx+1>fmx[u])fmxi[u]=fat,smx[u]=fmx[u],fmx[u]=mx+1;
	else if(mx+1>smx[u])smx[u]=mx+1;
	for(int i=0;i<e[u].size();i++)
	{
		int v=e[u][i];
		if(v==fat)continue;
		dfs2(v,u);
	}
}
void ini_dis(int u,int fat)
{
	for(int i=0;i<e[u].size();i++)
		if(e[u][i]!=fat)
		{
			int v=e[u][i];
			dis[v]=dis[u]+1;
			ini_dis(v,u);
		}
}
int dfs3(int u,int fat,int num)
{
	dep[u]=max(dis[u]-num,0);
	int res=0;
	for(int i=0;i<e[u].size();i++)
	{
		int v=e[u][i];
		if(v==fat)continue;
		res+=dfs3(v,u,num);
		dep[u]=max(dep[u],dep[v]);
	}
	return res+(dis[u]<=dep[u]?1:0);
}
int ck(int rt,int num)
{
	memset(dep,0,sizeof dep);
	return dfs3(rt,0,num)<=k;
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0);
	cin>>n>>k;
	int u,v;
	for(int i=1;i<n;i++)
		cin>>u>>v,e[u].push_back(v),e[v].push_back(u);
	dfs1(1,0);
	dfs2(1,0);
	int rt=1;
	for(int i=1;i<=n;i++)
		if(fmx[rt]>fmx[i])rt=i;
	ini_dis(rt,0);
	int l=-1,r=n-1,mid;
	while(l<r-1)
	{
		mid=(l+r)>>1;
		if(ck(rt,mid))r=mid;
		else l=mid;
	}
	cout<<r;
	return 0;
}/*
8 5
1 6
2 5
2 8
3 8
3 6
4 8
4 7

*/