Problem Statement:

You are given a binary tree consisting of n nodes numbered from 0 to n - 1 and a table events where events[i] = [vi, hi]. Each event i starts at the time vi, and consists of a height change of hi to a subtree rooted at node vi.

We define the subtree of a node as the node and all its descendants. A subtree removal is the process of removing the subtree rooted at a node.

The height of a binary tree is the number of edges between the tree's root and its furthest leaf.

Implement a function called max_height which returns an array containing the heights of the binary tree after each subtree removal operation.

Input:

The input consists of the following:

• An integer n (1 <= n <= 10^5) representing the number of nodes in the binary tree.
• An array edges containing n - 1 edges. Each edge is represented by a pair [u, v], where u and v are integers representing the nodes.
• An integer q (1 <= q <= 10^5) representing the number of events.
• An array events containing q events. Each event is represented by a pair [v, h], where v and h are integers representing the node index and the height change, respectively.

Output:

Return an array containing the heights of the binary tree after each subtree removal operation. The length of the output array should be equal to q.

Example:

Input: n = 5, edges = [[0,1],[0,2],[1,3],[0,4]], events = [[2,1],[0,-1],[3,1],[4,-1]]

Output: [3,2,2,3]

Explanation: The tree initially looks like this:

  0
/ | \

1 2 4 / 3

The height of the tree is 2. The first event is to increase the height of node 2 by 1. After this, the tree looks like this:

   0
/  |  \

1 2' 4 / 3

The height of the tree is still 2. The second event is to decrease the height of node 0 by 1. This removes the subtree rooted at node 1. After this, the tree looks like this:

0'
2'
4

The height of the tree is now 1. The third event is to increase the height of node 3 by 1. After this, the tree looks like this:

0'
2'
4 | 3'

The height of the tree is still 1. The fourth event is to decrease the height of node 4 by 1. This removes the subtree rooted at node 4. After this, the tree looks like this:

0'
2'

The height of the tree is now 2. Therefore, the output is [3,2,2,3].

Solution:

The problem is solved using a post-order traversal of the tree in order to calculate the height of each subtree after each event. The basic idea is that we initialize a variable to keep track of the current height of the tree, and update it after each event. We also use an array to keep track of the height of each node.

The first step is to build the tree using the edges array. We construct the tree as an adjacency list for each node, keeping track of its children. We also initialize the height of each node to 0.

The next step is to traverse the tree using a post-order traversal. This will allow us to calculate the height of each node after each event. In a post-order traversal, we first visit the left child, then the right child, and finally the parent. We calculate the height of each node by taking the maximum height of its children and adding 1 (the edge between the parent and the node).

After calculating the height of the tree, we can update it based on each event. If an event is to increase the height of a subtree, we add the height change to all nodes in the subtree. If an event is to decrease the height of a subtree, we subtract the height change from all nodes in the subtree and set the height of the root node of the subtree to 0 (since we are removing the subtree).

Finally, we add the current height of the tree to the result array after each event.

The time complexity of this algorithm is O(n + q), where n is the number of nodes in the tree and q is the number of events. The space complexity is O(n), since we use an adjacency list to represent the tree. Here is the implementation of the solution in Python:

def max_height(n, edges, events):

# Step 1: Build the tree
adj = [[] for i in range(n)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)

# Initialize node height to 0
height = [0] * n

# Step 2: Post-order traversal to calculate subtree height
def dfs(node, parent):
    nonlocal height
    for child in adj[node]:
        if child != parent:
            dfs(child, node)
            height[node] = max(height[node], height[child])
    height[node] += 1

dfs(0, -1)
curr_height = height[0]

# Step 3: Update height based on events
res = [curr_height]
for node, change in events:
    if change > 0:
        # Increase height of subtree rooted at node
        q = [node]
        while q:
            curr = q.pop(0)
            height[curr] += change
            for child in adj[curr]:
                if height[child] < height[curr]:
                    q.append(child)
    
    elif change < 0:
        # Decrease height of subtree rooted at node
        q = [node]
        while q:
            curr = q.pop(0)
            height[curr] += change
            if curr == node:
                height[curr] = 0
            for child in adj[curr]:
                if height[child] < height[curr]:
                    q.append(child)
    
    curr_height = max(height)
    res.append(curr_height)

return res

Example test case

n = 5 edges = [[0,1],[0,2],[1,3],[0,4]] events = [[2,1],[0,-1],[3,1],[4,-1]] assert max_height(n, edges, events) == [3,2,2,3]

1