P9597 [JOI Open 2018] Cats or Dogs / Cats or Dogs

**Special reminder: due to Luogu’s special interaction mechanism, you cannot include `catdog.h` in your program. You only need to implement the required functions.**

Your son, JOI, likes keeping pets. In your garden, there are $N$ huts for keeping pets, numbered from $1$ to $N$. There are $N-1$ undirected paths connecting these $N$ huts, and for any two huts, it is possible to move between them along some paths. Each hut can contain at most one pet. JOI wants to keep cats and dogs, but he is worried that the pets may often fight. For each of the following states of the huts: having a cat, having a dog, or being empty, he defines the garden’s **danger level** as follows: - For every cat and every dog, the minimum number of paths that need to be blocked so that they cannot meet via unblocked paths. After defining the danger level, JOI starts to make a plan for using the garden over the next $Q$ days. Initially, all huts are empty. The plan for day $i$ is one of the following: - Keep a cat in an empty hut $v$. - Keep a dog in an empty hut $v$. - Give the pet in hut $v$ to a neighbor, meaning hut $v$ becomes empty. As a parent, you are responsible for checking whether your son’s plan is dangerous. More precisely, you need to compute the danger level of the garden after each day’s plan is carried out, for all $Q$ days. --- **To answer queries online, this problem is judged in an interactive manner.** You need to implement four functions: `initialize`, `cat`, `dog`, and `neighbor`. At the beginning, the function `initialize` is called. This function receives the garden information. - `initialize(N, A, B)` - $N$: the number of huts in the garden. - $A, B$: arrays of length $N-1$. This means that for $0 \le i \le N-2$, there is a path between huts $A_i$ and $B_i$. It is guaranteed that for any two different huts, it is possible to move between them along some paths. Then, for the plans over these $Q$ days, the following functions are called in chronological order: - `cat(v)`: call this function to keep a cat in an empty hut $v$. - `dog(v)`: call this function to keep a dog in an empty hut $v$. - `neighbor(v)`: call this function to make the pet in hut $v$ leave. These functions should return the garden’s danger value after the plan is executed. Submissions in Java and Pascal are currently not supported.

The sample interactor reads input in the following format: The first line contains an integer $N$. The next $N-1$ lines each contain two integers $A_i, B_i$. The next line contains an integer $Q$. The next $Q$ lines each contain two integers $T_j, v_j$. Here, if the call on day $j$ is $\texttt{cat}$, then $T_j = 1$; if it is $\texttt{dog}$, then $T_j = 2$; if it is $\texttt{neighbor}$, then $T_j = 3$.

The sample interactor outputs the function call result $D_j$ for day $j$ in the following format: On the $j$-th line, output $D_j$.

**Sample** Consider the case with $5$ huts and $4$ paths. These four paths connect hut $1$ and hut $2$, hut $2$ and hut $3$, hut $2$ and hut $4$, and hut $4$ and hut $5$. 1. Suppose he first keeps a cat in hut $3$ and a dog in hut $5$. By blocking the path between hut $2$ and hut $4$, he can prevent the cat and the dog from meeting. Therefore, the danger level at this time is $1$. 2. Suppose he then keeps a new cat in hut $2$ and a new dog in hut $1$. By blocking the path between hut $2$ and hut $4$ and the path between hut $1$ and hut $2$, he can prevent cats and dogs from meeting. Therefore, the danger level at this time is $2$. 3. Suppose he finally gives the cat in hut $2$ to a neighbor. He only needs to block the path between hut $2$ and hut $3$. Therefore, the danger level at this time is $1$. **Constraints** This problem has three subtasks. The score and additional constraints for each subtask are shown in the table below: | Subtask ID | Score | $N$ | $Q$ | | :--------: | :---: | :------------------: | :------------------: | | $1$ | $8$ | $1 \le N \le 15$ | $1 \le Q \le 100$ | | $2$ | $30$ | $1 \le N \le 1\ 000$ | $1 \le Q \le 1\ 000$ | | $3$ | $62$ | $1 \le N \le 100\ 000$ | $1 \le Q \le 100\ 000$ | Translated by ChatGPT 5