CF1385F Removing Leaves

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.