问题2944--树的切割(cut)

2944: 树的切割(cut)

时间限制: 14 Sec  内存限制: 512 MB
提交: 4  解决: 3
[提交] [状态] [讨论版] [命题人:]

题目描述

给定一棵n个点的树,求至少删去多少个点(删点时同时删去所有连接这个点的边)使剩下的点仍然连通,且树的直径不超过k。

输入

多组测试数据。第一行包含一个整数T(1≤T≤15),表示有T组测试数据。
对于每组测试数据,第一行2个整数n,k (1≤n,k≤300000) 。
接下来n-1行每行两个正整数u,v(1≤u,v≤n,u≠v),表示u,v间有一条长为1的边。

输出

对于每组数据,输出一行1个整数,表示最少删掉点的数量。

样例输入 Copy

1
10 3
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10

样例输出 Copy

4