P9620 Songstress

> Are you satisfied with this? > > Have you never thought about making it happen? > > Made for you, made for you. > > The poor system turns into a gentle duty.

Right now, *26 has $n$ matters in mind, and they form a tree. Each matter has two states: real and want. Initially, all matters are want. Assume matter $1$ is the root of this tree in the mind. Then the depth of a matter $u$ is defined as the number of matters on the simple path from matter $1$ to matter $u$ (including both endpoints). We call a set of matters $S$ a real connected component if it satisfies: for any two real matters on the tree, all matters on the simple path between them (including endpoints) also belong to $S$. The minimal real connected component is the real connected component with the smallest number of matters. As time goes by, the states of matters may change. Below, *26 mentions $m$ changes of matters to you. Each change is one of the following two types: 1. `Real u`: matter $u$ becomes real. 2. `Want u`: matter $u$ becomes want. After each change, *26 will ask you: at least how many additional matters still need to be changed into want, so that the position of the matter with the minimum depth in the minimal real connected component changes, or so that there are no real matters in the mind at all.

The first line contains two integers $n, m$, representing the number of matters and the number of changes. The next $n - 1$ lines each contain two integers, representing an edge of the tree. The next $m$ lines are in the form `Real u` or `Want u`, representing one change. Here $1 \le u \le n$.

Output $m$ lines. Each line contains one integer, representing the answer you provide to *26 after the $i$-th change.

### Explanation for Sample #1 Consider the situation after the last change. At this time, on the tree, except for matters $1,3,7$ which are want, all other matters are real. Then the minimal real connected component is $\{1,2,4,5,6\}$. $\{2,4,5,6\}$ is not a minimal real connected component, because there exist two real matters such as $2$ and $6$, whose simple path passes through $1$, but $1$ is not in the set $\{2,4,5,6\}$. $\{1,2,3,4,5,6\}$ is also not a minimal real connected component, because there exists a real connected component $\{1,2,4,5,6\}$ whose size is smaller than it. When we change matters $2$ and $4$ into want, the only real matters left are $5$ and $6$. Then the minimal real connected component is $\{5,6\}$. The matter with the minimum depth changes from $1$ to $5$. It can be proven that this strategy is one of the optimal strategies. ### Constraints |Test Point ID|Constraints| |:-:|:-:| |$1,2$|$1 \le n,m \le 20$| |$3,4,5$|$1 \le n,m \le 300$| |$6,7,8$|$1 \le n,m \le 3000$| |$9,10,11,12$|$1 \le n, m \le 39393$| |$13 \sim 20$|$1 \le n, m \le 2 \times 10^5$| For all testdata, it is guaranteed that at any operation, the state of the matter before the change and after the change is different. Translated by ChatGPT 5