#P17891. Lice Hopping
Lice Hopping
给定一棵有 个结点的树。你可以从任意结点出发,每次跳到与当前位置距离不超过 的另一个结点。树上距离为简单路径上的边数。
要求每个结点恰好作为起点或某次跳跃的落点出现一次。跳跃途中经过的结点不算访问,也不影响它以后作为落点。
求能够访问全部结点的最小整数 。
输入格式
第一行测试用例数 ,。
每组第一行整数 ,。接着 行各包含两个整数 ,表示一条边,,。输入保证是一棵树。
所有测试用例的 之和不超过 。
输出格式
每组输出一个整数,表示最小的 。
样例
4
3
1 2
1 3
5
1 2
1 3
1 4
1 5
7
1 2
1 3
2 4
2 5
3 6
3 7
15
1 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
5 10
5 11
6 12
6 13
7 14
7 15
1
2
2
2
第一组可按 访问。第四组可按
访问,相邻落点的树上距离均不超过 。