Removing Leaves
Contest: Codeforces Round 656 (Div. 3)
Difficulty rating: 2300
Tags: 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.

Input format:
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$$$).

Output format:
For each test case, print the answer — the maximum number of moves you can perform if you remove leaves optimally.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
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

Example output:
2
3
3
4

Editorial:
This is mostly implementation problem. We can notice that all leaves are indistinguishable for us. So if we have some vertex with at least $$$k$$$ leaves attached to it, we can choose it, remove these leaves from the tree and continue the algorithm. The rest is just an implementation: let's maintain for each vertex $$$v$$$ the list of all leaves which are connected to it $$$leaves_v$$$ and the set of vertices which is sorted by the size of $$$leaves_v$$$. So let's take any vertex which Is connected with at least $$$k$$$ leaves (we can just take the vertex with the maximum value in the set) and remove any $$$k$$$ leaves attached to it. If it has zero leaves after the current move, let's mark is as a leaf and append it to the list of the corresponding vertex (you also need to remove edges from the graph fast to find the required vertex, so you may need to maintain the graph as the list of sets). And don't forget about the case $$$k=1$$$ because it may be special for your solution so you could handle it in a special way.
Time complexity: $$$O(n \log{n})$$$.