N-ary Tree Height After Deleting Nodes and Reattaching Their Children

A rooted tree has n nodes numbered 0 to n - 1, and each node can have any number of children. Node 0 is the root. You are given the tree as a parent array, together with a list of nodes to delete.

When a node is deleted, its children are attached to the deleted node's parent. If that parent is deleted as well, the children move up again, so in the end every remaining node hangs directly under its nearest ancestor that is not deleted.

Return the height of the tree that remains after all the deletions.

Function Signature

def height_after_deletions(parent: list[int], deleted: list[int]) -> int:

parent[i] is the parent of node i, and parent[0] == -1. deleted lists the nodes to delete.

Rules

• The height of a tree is the number of nodes on its longest path from the root down to a leaf. A tree that consists of the root alone has height 1.
• The root is never deleted.
• Apart from the reattachment described above, the tree does not change. The remaining tree, and therefore the answer, does not depend on the order of deleted.

Constraints

• 1 <= len(parent) <= 10^5
• parent[0] == -1. For i >= 1, 0 <= parent[i] < len(parent) and parent[i] != i, and following parents from any node reaches node 0, so the input is a single tree. A parent's number may be larger than its child's.
• 0 <= len(deleted) <= len(parent) - 1. The entries of deleted are distinct, and each lies between 1 and len(parent) - 1.
• The tree may be a single path of 10^5 nodes.

Examples

Example 1

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

The tree has the edges 0 → 1, 0 → 2, 1 → 3, 1 → 4, 3 → 5 and 2 → 6, and its longest path, 0 → 1 → 3 → 5, has 4 nodes. Deleting node 3 attaches node 5 to node 1, so every path now has at most 3 nodes.

Example 2

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

The tree is the path 0 → 1 → 2 → 3 → 4. Node 4 belonged to node 3, whose parent, node 2, is also deleted, so node 4 ends up under node 1. The remaining tree is 0 → 1 → 4.

Example 3

Input: parent = [-1, 3, 0, 2, 1], deleted = [2]
Output: 4

The tree is the path 0 → 2 → 3 → 1 → 4. Deleting node 2 attaches node 3 to the root, leaving 0 → 3 → 1 → 4.