代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,k,cnt,b[200001],an,ans;
int c[200001];
vector<int> x[200001];
void dfs(int wz,int last){
	b[wz]=0;
	int jsq=0;
	for(int i=0;i<x[wz].size();i++){
		if(x[wz][i]!=last){
			dfs(x[wz][i],wz);
			if(c[x[wz][i]]==0) b[wz]++;
			else jsq++;
		}
	}
	c[wz]=jsq+b[wz]%k;
//	cout<<b[wz]<<' '<<wz<<" 114514"<<endl;
	ans+=b[wz]/k;
}
void dp(int wz,int last,int cnt){
	for(int i=0;i<x[wz].size();i++){
		if(x[wz][i]!=last){
			int o=cnt,p=0,pp=0;
			if(b[wz]%k==0&&c[x[wz][i]]==0) o--;
			if(((c[wz]==1&&(c[x[wz][i]]!=0||b[wz]%k==1))||c[wz]==0)){
				//cout<<c[wz]<<' '<<c[x[wz][i]]<<' '<<b[x[wz][i]]<<endl;
				if(b[x[wz][i]]%k==k-1)o++;
				else c[x[wz][i]]++,pp++;
				p++;
				b[x[wz][i]]++;
			}
			else pp++,c[x[wz][i]]++;
			//if(o>an) cout<<o<<' '<<x[wz][i]<<" 1145"<<endl;
			an=max(o,an);
			dp(x[wz][i],wz,o);
			if(p!=0) b[x[wz][i]]--;
			if(pp!=0) c[x[wz][i]]--;
		}
	}
}
signed main(){
	cin>>t;
	while(t--){
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		cin>>n>>k;
		int u,v;
		ans=0;
		for(int i=1;i<n;i++){
			cin>>u>>v;
			x[u].push_back(v);
			x[v].push_back(u);
		}
		dfs(1,0);
		an=ans;
		//cout<<an<<' ';
		dp(1,0,ans);
		cout<<an<<endl;
		for(int i=1;i<=n;i++) x[i].clear();
	}
	return 0;
}/*
4
8 3
1 2
1 5
7 6
6 8
3 1
6 4
6 1
10 3
1 2
1 10
2 3
1 5
1 6
2 4
7 10
10 9
8 10
7 2
3 1
4 5
3 6
7 4
1 2
1 4
5 1
1 2
2 3
4 3
5 3
*/