Remove and Compact a Parent-Index Forest

Problem Statement

You are given an array parent of length n, representing a forest (a collection of disjoint trees) with nodes labeled 0 to n - 1. For each node i:

• parent[i] is the index of its parent node.
• If parent[i] == -1, node i is the root of a tree.

You are also given an integer target (0 <= target < n). You must remove target and all of its descendants from the forest.

After removing these nodes:

1. The surviving nodes must preserve their original relative order.
2. The surviving nodes must be re-indexed (compacted) to 0, 1, ..., k - 1, where k is the number of surviving nodes.
3. Every surviving node's parent reference must be updated to point to the new index of its parent, or -1 if it is a root.

Return the new compacted parent array. Do not mutate the original parent array.

Function Signature

def compact_forest(parent: list[int], target: int) -> list[int]:
    pass

Constraints

• 1 <= len(parent) <= 10^5
• parent[i] == -1 or 0 <= parent[i] < len(parent)
• The input graph is a valid forest (acyclic, each node has at most one parent).
• 0 <= target < len(parent)

Examples

Example 1

Input: parent = [-1, 0, 0, 1, 2], target = 1
Output: [-1, 0, 1]

Explanation:

• The forest structure is:
  • Root 0 has children 1 and 2.
  • Node 1 has child 3.
  • Node 2 has child 4.
• Removing 1 and its descendants removes nodes {1, 3}.
• Surviving nodes in original order: [0, 2, 4].
• New index mapping: 0 -> 0, 2 -> 1, 4 -> 2.
• Updating parents:
  • New node 0 (old 0): parent was -1 -> -1
  • New node 1 (old 2): parent was 0 -> new index 0
  • New node 2 (old 4): parent was 2 -> new index 1
• Result: [-1, 0, 1].

Example 2

Input: parent = [-1, 0, 1], target = 0
Output: []

Explanation: Node 0 is the root and both 1 and 2 are its descendants. Removing 0 removes all nodes.

Edge Cases to Consider

• Removing a leaf node (only one node is removed).
• Removing a root of a tree in a multi-tree forest (other trees remain unaffected).
• The entire forest is removed (returns an empty list).