Subtree Pruning II
The same tree shape: a parent array with parent[0] = -1, node 0 the root at depth 0. Deleting a node removes it and its whole subtree. The root cannot be deleted, and every node already within the limit must stay.
Return the fewest deletions that leave every remaining node at depth at most k.
fewestCuts([-1, 0, 0, 1, 1, 3], 2) -> 1 // only node 5, at depth 3, is too deep fewestCuts([-1, 0, 0, 1, 1, 2, 2], 1) -> 4 // the four depth-2 nodes each need their own cut
Hints
Hint 1
Which nodes are even allowed to be deleted? Only the ones past the limit — and deleting one of those removes everything below it.
Hint 2
So the first too-deep node on every root-to-leaf path has to go, and nothing else can; count them.