Tree Cutting

Given a tree (connected undirected graph with $n$ vertexes and $n - 1$ edges), you are required to delete as few vertexes as possible such that the remaining graph is still a tree and its diameter shall not exceed $k$. The diameter of a tree is the length of its longest path.

The first line contains one positive integer $T$ ($1\le T \le 15$), denoting the number of test cases. For each test case:

The first line of the input contains two integers $n, k\,(1\le n,k \le 300000)$.

Each of the following $n - 1$ lines contains two integers $u, v\, (1\le u,v \le n, u\neq v)$, indicating that there is an edge connecting vertex $u$ and $v$ in the tree.

For each test case:

You should just output one integer indicating the number of vertexes to be deleted.

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

4

2020 Multi-University Training Contest 10