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.

N/A

N/A

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.