Hints: Tree Cutting

Suppose $x$ is fixed. Can you figure out if it’s possible to make exactly $k$ cuts such that each connected component has size at least $x$?

In these type of problems, dealing with the version “exactly equal to something” is a bit tricky. Can we relax the criteria to $\leq k$ or $\geq k$?

Which one works and why?

If you have a configuration where each connected component has size $\geq x$, and there are $k + 1$ cuts made, can you achieve a configuration where you made exactly $k$ cuts?

Note that there’s no harm in ignoring a cut. Therefore, if we can find out the maximum number of cuts that we can make such that each connected component has size at least $x$, then, to answer the question of exactly equal to $k$, we just need to check if $max\_cut \geq k$.

So, this is the final easy version of the problem.

Given a tree, what is the maximum number of cuts that you can make such that each connected component has size $\geq x$?

Start with leaf vertices.

Start with leaf vertices. If they are not cut, merge it into its parent, creating a mega node. Once all the leaves are processed, the parents would become leaves. So repeat the process, but this time, the size of each leaf would be equal to the number of children it has eaten.

Now, apply binary search on answer. Why does it work?