P6729 [WC2020] Rooted Tree

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)$.

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.

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

#### 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\}$. | Test Point ID | $n \le$ | $q \le$ | Special Restriction | | ------------ | ---------------- | ---------------- | ------------------- | | $1 \sim 2$ | $100$ | $500$ | None | | $3 \sim 4$ | $2 \times 10^4$ | $2 \times 10^4$ | None | | $5 \sim 6$ | $10^5$ | $2 \times 10^5$ | A | | $7 \sim 8$ | $2 \times 10^5$ | $4 \times 10^5$ | B | | $9 \sim 11$ | $2 \times 10^5$ | $4 \times 10^5$ | C | | $12 \sim 16$ | $2 \times 10^5$ | $4 \times 10^5$ | None | | $17 \sim 20$ | $5 \times 10^5$ | $10^6$ | None | 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