Delete a Subtree in a Parent Array and Compact Deleted Nodes

Problem: Delete a Subtree in a Parent Array and Compact Deleted Nodes You are given an array parent of length n, representing a rooted tree where array indices are node IDs: Nodes are labeled from 0 to n - 1. parent[i] is the parent index of node i. The root node satisfies parent[root] == root. The input is guaranteed to be a valid rooted tree. You are also given an integer target, representing the node to delete. Complete two tasks: Find target and all descendants of target, mark their positions in the parent array as -1, and output the marked array. Move all -1 entries to the right side of the array while preserving the relative order of the remaining nodes. Because node indices change after compaction, update the parent indices of all remaining nodes. Output the compacted array of length n; deleted positions on the right should be -1. Input Format n parent[0] parent[1] ... parent[n-1] target Output Format Print two lines: the marked parent array the compacted parent array with remapped indices Constraints 1 <= n <= 200000 0 <= target < n 0 <= parent[i] < n There is exactly one root node root such that parent[root] == root. The input is guaranteed to be a valid tree. Example Input: 6 0 0 0 1 1 2 1 The subtree rooted at node 1 contains {1, 3, 4}. Output: 0 -1 0 -1 -1 2 0 0 1 -1 -1 -1 Example Input 6 0 0 0 1 1 2 1 Output 0 -1 0 -1 -1 2 0 0 1 -1 -1 -1