F. Removing Leaves
data structures; greedy; implementation; trees
You are given a tree (connected graph without cycles) consisting of \(n\) vertices. The tree is unrooted — it is just a connected undirected graph without cycles.In one move, you can choose exactly \(k\) leaves (leaf is such a vertex that is connected to only one another vertex) connected to the same vertex and remove them with edges incident to them. I.e. you choose such leaves \(u_1, u_2, \dots, u_k\) that there are edges \((u_1, v)\), \((u_2, v)\), \(\dots\), \((u_k, v)\) and remove these leaves and these edges.Your task is to find the maximum number of moves you can perform if you remove leaves optimally.You have to answer \(t\) independent test cases.
The first line of the input contains one integer \(t\) (\(1 \le t \le 2 \cdot 10^4\)) — the number of test cases. Then \(t\) test cases follow.The first line of the test case contains two integers \(n\) and \(k\) (\(2 \le n \le 2 \cdot 10^5\); \(1 \le k < n\)) — the number of vertices in the tree and the number of leaves you remove in one move, respectively. The next \(n-1\) lines describe edges. The \(i\)-th edge is represented as two integers \(x_i\) and \(y_i\) (\(1 \le x_i, y_i \le n\)), where \(x_i\) and \(y_i\) are vertices the \(i\)-th edge connects. It is guaranteed that the given set of edges forms a tree.It is guaranteed that the sum of \(n\) does not exceed \(2 \cdot 10^5\) (\(\sum n \le 2 \cdot 10^5\)).
For each test case, print the answer — the maximum number of moves you can perform if you remove leaves optimally.
The picture corresponding to the first test case of the example:There you can remove vertices \(2\), \(5\) and \(3\) during the first move and vertices \(1\), \(7\) and \(4\) during the second move.The picture corresponding to the second test case of the example:There you can remove vertices \(7\), \(8\) and \(9\) during the first move, then vertices \(5\), \(6\) and \(10\) during the second move and vertices \(1\), \(3\) and \(4\) during the third move.The picture corresponding to the third test case of the example:There you can remove vertices \(5\) and \(7\) during the first move, then vertices \(2\) and \(4\) during the second move and vertices \(1\) and \(6\) during the third move.