Level 1 Height after deletions
A rooted tree with n nodes (0..n-1, any number of children each) is given as a parent list: parent[v] is v's parent, and exactly one node has parent[v] == -1 (the root). Node ids aren't in any particular order. n may be 0.
Deleting a node removes it but keeps its descendants: each child moves up and hangs off the nearest ancestor that wasn't deleted. If the root is deleted, its surviving children become roots of separate trees, so you get a forest.
Height is counted in levels (nodes on the longest root-to-leaf path), so a single node has height 1 and an empty forest has height 0.
Write height_after_deletion(parent: list[int], deleted: set[int]) -> int, the largest height in the forest that remains.
Put another way, for every node, count the non-deleted nodes on its path to the original root and take the maximum.
Trees can have 100,000 nodes and be one long path, so avoid recursion and don't walk to the root from every node.
# 0
# / \
# 1 2
# / \ \
# 3 4 5
# \
# 6
parent = [-1, 0, 0, 1, 1, 2, 5]
height_after_deletion(parent, set()) # 4 (0-2-5-6)
height_after_deletion(parent, {2}) # 3 (5 moves up under 0: 0-5-6)
height_after_deletion(parent, {0, 5}) # 2 (forest: 1-3, 1-4, 2-6)