Find Tree Height After Deleting Nodes and Promoting Children

Delete selected nodes from a rooted multiway tree. Deleting a node promotes all of its children to its parent; it does not delete the descendants. Return the final tree height measured in nodes along the longest root-to-leaf path. Implement `height_after_deletions(parent: int[], deleted: int[]) -> int`. ### Constraints & Assumptions - The tree has `1 <= n <= 200000` nodes with unique IDs `0..n-1`. Node 0 is the root, `parent[0] == -1`, and each other entry identifies its parent. This array is a practice representation of the source's unique node values. - The parent array describes a valid tree but parent IDs need not be smaller than child IDs. - Every deleted ID is a non-root node. Duplicate deleted IDs have no extra effect. - Any number of non-root nodes may be deleted. A root-only result has height 1. - Only the height is required; do not construct a rewritten tree merely to return it. - Aim for O(n + len(deleted)) time. Account for traversal depth when choosing recursive or iterative code. ### Examples ```text parent = [-1,0,0,2,2,4], deleted = [2] result = 3 ``` The retained path `0 -> 4 -> 5` has three nodes after node 2's children are promoted. ```text parent = [-1,0,1,2], deleted = [1,2] result = 2 ``` Explain why deleting an internal node reduces the contribution of that node but preserves the descendants' contribution. Include tests for the root-only tree, no deletions, consecutive deleted ancestors, and all non-root nodes deleted, and state time and space complexity. ```hint Count retained nodes on original paths Promotion changes edges, but the surviving order of nodes along an original root-to-leaf path is unchanged. ```