Minimize Tree Height with K Cut & Attach-to-Root Operations

Turn height into a decision problem

For a target height H, ask whether at most k cut-and-attach operations can make every node depth at most H. Root the tree at the specified root and process nodes from deepest to shallowest. When an uncovered node is deeper than H, choose the ancestor whose reattachment covers the largest still-problematic portion allowed by the operation, mark that subtree handled, and increment the operation count. The exact ancestor offset must follow the statement's cut semantics, so articulate it before implementation.

Why deepest-first matters

A deepest violating node has to be affected by some operation on its root path. Selecting the highest ancestor that can still repair it also repairs every applicable descendant, so postponing it cannot cover more nodes. This gives a greedy feasibility check. Since a larger H cannot need more operations, binary-search H. With preprocessing for parents/depths and a linear feasibility pass, the usual bound is O(n log n) time and O(n) space; the exact marking method may use Euler-tour intervals. Test a chain, an already shallow tree, k=0, and operations that attach a child rather than the subtree root.