Description

Given a rooted tree with $n$ nodes, the nodes are numbered from $1 \sim n$, and node $1$ is the root. Xiaoming has a node set $S$. For a node $u$ in $S$, he defines the value $w_u$ as the number of nodes in the subtree of $u$ (including $u$ itself) that are contained in the set $S$. For convenience, for nodes not in $S$, we consider $w_u = 0$.

Next, Xiaoming needs you to choose a connected component $C$ that contains the root. Let $a$ be the number of nodes in $C$ that are contained in $S$, and let $b$ be the maximum $w$ value among the nodes not in $C$. If there is no node outside $C$, then $b = 0$. Xiaoming wants you to minimize $\max(a,b)$.

Xiaoming thinks this problem is quite simple, so he also provides $q$ operations. Each operation will insert or delete one node in the set $S$. For the set $S$ after each operation, please output the minimum possible value of $\max(a,b)$.

Input Format

The first line contains a positive integer $n$, indicating the number of nodes.

The next $n - 1$ lines each contain two integers $x, y$, indicating an edge $(x,y)$ in the tree.

The next line contains a positive integer $q$, indicating the number of operations.

The next $q$ lines each contain two numbers $t, v$, indicating an operation. If $t = 1$, the operation inserts node $v$ into $S$, and it is guaranteed that before the operation $v \notin S$. If $t = 2$, the operation deletes node $v$ from $S$, and it is guaranteed that before the operation $v \in S$. Initially, $S$ is empty.

Output Format

After each operation, output one line with one integer indicating the answer.

5
1 2
1 3
1 4
2 5
5
1 4
1 1
1 2
1 5
2 2

1
1
1
2
1

Hint

Sample Explanation

After the first operation, $S = \{4\}$. One possible choice is $C = \{1\}$, and then $a = 0, b = 1$.

After the second operation, $S = \{1,4\}$. One possible choice is $C = \{1\}$, and then $a = 1, b = 1$.

After the third operation, $S = \{1,2,4\}$. One possible choice is $C = \{1\}$, and then $a = 1, b = 1$.

After the fourth operation, $S = \{1,2,4,5\}$. One possible choice is $C = \{1,2\}$, and then $a = 2, b = 1$.

After the fifth operation, $S = \{1,4,5\}$. One possible choice is $C = \{1\}$, and then $a = 1, b = 1$.

Constraints

For all test points: $1 \le n \le 5 \times 10^5$, $1 \le q \le 10^6$, $1 \le x, y, v \le n$, $t \in \{1,2\}$.

The meanings of the symbols in the “Special Restriction” column are:

A: At any time, the size of the set $S$ does not exceed $50$.

B: The tree is a chain, and node $1$ has degree $1$.

C: For every node in the tree, its parent node index is smaller than itself, $n = q$, and the $i$-th operation inserts node $i$ into $S$.

Translated by ChatGPT 5