This problem appeared as Problem F in one of the recent Div3s. The problem goes as follows -

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 u1,u2,…,uk that there are edges (u1,v), (u2,v), …, (uk,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.

N <= 10^5 and K<N

I started wondering about slightly different variant of the problem where the condition that the K leaves we pick must be connected to the same vertex no longer holds. Basically we can pick any K leaf nodes as one move and we need to maximise our moves. Does anyone have a solution for this problem? Game theory is not my strong suit and i can't think of any other approach for this, any ideas are appreciated. Thanks for your time.