Minimizing the Maximum of Subtree Counts in a Rooted Tree

You are given a rooted tree with n nodes numbered from 1 to n, with node 1 being the root. We also have a set S of nodes. For any node u, define its weight w_u by:

\(w_u=\begin{cases}\text{the number of nodes in the subtree of } u \text{ (including } u \text{ itself) that belong to } S, & u\in S,\\0, & u\notin S.\end{cases}\)

You need to choose a connected block C (a connected set of nodes) that must include the root. Let:

• a be the number of nodes in C that belong to S, and
• b be the maximum weight w_u among all nodes u not in C (if every node is in C, then take \(b = 0\)).

Your task is to choose C so that \(\max(a, b)\) is minimized.

Furthermore, there are q operations. Initially, the set S is empty. Each operation either adds a node to S or removes a node from S. After every operation, you have to output the minimum possible value of \(\max(a, b)\) (over all connected blocks C containing the root) for the current set S.

Note: For a given candidate value \(M\), the following observation is useful. In order for a connected block C to satisfy \(\max(a, b) \le M\), it is necessary that all nodes u with \(w_u > M\) are included in C (because otherwise \(b\), which is at least \(w_u\), would exceed \(M\)). Since C is required to be connected and contain the root, that forces us to include the entire path from the root to every such u. Let the union of all such paths be the forced set; if the number of nodes from S in this set exceeds \(M\), then \(M\) is not feasible. The answer is the minimum feasible \(M\).

inputFormat

The first line contains two integers n and q (number of nodes and number of operations).

The second line contains n - 1 integers: p2, p3, ..., pn, where pi is the parent of node i (for i = 2, 3, \dots, n).

Then follow q lines. Each line contains two integers op and x:

• If op = 1, add node x to S (if not already present).
• If op = 0, remove node x from S (if it is present).

It is guaranteed that all operations are valid.

outputFormat

For each operation, output one integer — the minimum possible value of \(\max(a, b)\) after the operation.

sample

3 3
1 1
1 2
1 3
0 2

1
1
1

</p>