Minimize Tree Height with K Reattachments

Problem Given a rooted tree, you may perform at most K operations. Each operation cuts any subtree away from its parent and re-attaches it directly under the root. Minimise the height of the resulting tree and return that minimum height.

Input / Output

• Input: a rooted tree (parent array or adjacency list) and an integer K.
• Output: the minimum achievable height after at most K cut-and-attach operations.

Constraints

• Up to ~10^5 nodes; 0 <= K <= n.
• The tree may be arbitrarily shaped, including a fully skewed chain of depth n.
• Operations are sequential — a subtree hoisted to the root may itself contain further subtrees you later hoist.

Example

• A path 1 -> 2 -> 3 -> 4 -> 5 rooted at 1 has height 4. With K=1, cutting the subtree rooted at 4 and attaching it under 1 leaves heights 1->2->3 and 1->4->5, giving height 2.
• Tricky case: K large enough to hoist every node yields height 1 (a star); K=0 returns the original height unchanged.