求hack

#include<bits/stdc++.h>
using namespace std;
constexpr int N=2e5+5;
int n,m;
vector<int>e[N];
int cnt[N],siz[N],rt,ans;
inline void dfs(int u,int fa){
	int maxn=0;
	for(auto v:e[u]){
		if(v==fa)continue;
		dfs(v,u);maxn=max(maxn,siz[v]);
		++cnt[siz[v]];
	}
	if(maxn!=0)--cnt[maxn];
	else ++ans;
	siz[u]=maxn+1;
	if(u==rt){
		int ma2=0;maxn=0;
		for(auto v:e[u]){
			if(v==fa)continue;
			if(siz[v]>=maxn)ma2=maxn,maxn=siz[v];
			else if(siz[v]>=ma2)ma2=siz[v];
		}
		--cnt[ma2],++cnt[ma2+maxn];
	}
}
mt19937 rnd(time(NULL));
inline void solve()
{
	cin>>n>>m;
	for(int i=1,u,v;i<n;++i)cin>>u>>v,e[u].emplace_back(v),e[v].emplace_back(u);
	if(m<=2){
		cout<<m<<'\n';
		for(int i=0;i<=n;++i)e[i].clear(),cnt[i]=0;ans=0;
		return;
	}
	int minn=0x3f3f3f3f,c;
	for(int k=1;k<=40;++k){
		ans=0;
		for(rt=rnd()%n+1;1;rt=rnd()%n+1)if(e[rt].size()>=2)break;
		dfs(rt,0);
		c=n-m;
		for(int i=1;i<=n;++i){
			while(cnt[i]--){
				if(c>=i)--ans,c-=i;
			}
		}
		for(int i=0;i<=n;++i)cnt[i]=0;
		minn=min(minn,ans);
	}
	cout<<minn<<'\n';
	for(int i=0;i<=n;++i)e[i].clear();
}

signed main()
{
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int T;cin>>T;while(T--)solve();
	return 0;
}