P8998 [CEOI 2022] Prize (Interactive, Not Submittable)

**This is an interactive problem.** Tomislav thought of a problem in his sleep: given two trees of size $N$, the nodes in each tree are numbered $1\sim N$, and the trees are numbered Tree $1$ and Tree $2$. The trees have edge weights, but the edge weights are hidden. Tomislav needs to provide the interactive library with a subset $S$ of labels of size $K$. After choosing this set, Little C may ask $Q$ queries of the form $(a,b)$. Let $d_t(x,y)$ denote the distance between node $x$ and node $y$ in Tree $t$, and let $l_t$ be the LCA of nodes $a$ and $b$ in Tree $t$. The interactive library will answer, in order, $d_1(l_1,a),d_1(l_1,b),d_2(l_2,a),d_2(l_2,b)$. Then the interactive library will ask $T$ queries of the form $(p,q)$, where $p,q\in S$, and Tomislav must answer $d_1(p,q)$ and $d_2(p,q)$ in order. Poor Tomislav cannot solve it. Please help him.

The first line contains four integers $N,K,Q,T$. Next come two lines, each containing $N$ integers. The first line describes Tree $1$, and the second line describes Tree $2$. The description is as follows: $N$ integers $p_1,p_2,\ldots,p_N$ are given. If $p_i$ is $-1$, then $i$ is the root of the tree; otherwise, $p_i$ is the parent of $i$. Next, output $K$ integers $x_1,x_2,\ldots,x_K$ representing the set of labels $S$ provided by Little C. After outputting, flush the buffer. Then you may output at most $Q$ lines in the format `?` $a$ $b$, meaning you ask the query $(a,b)$. When your program stops asking, output a line `!` to indicate the end of queries. After outputting, flush the buffer. After you finish asking, the interactive library will return the answers to all queries. Each answer is on its own line, containing four integers $d_1(l_1,a),d_1(l_1,b),d_2(l_2,a),d_2(l_2,b)$, representing the response to that query. Next, $T$ lines follow. Each line contains two integers $p,q$, representing one query from the interactive library. Your program must answer these $T$ queries. Specifically, for each query, you need to output one line with two integers $d_1(p,q)$ and $d_2(p,q)$. After answering all queries, flush the buffer. There is a sample program in the additional files. This program can pass the sample below, and you can use it to understand the interaction process.

N/A

### Constraints and Notes For all testdata, it is guaranteed that all edge weights are positive integers and do not exceed $2000$, $2\le K\le 10^5$, and $1\le T\le \min(K^2,10^5)$. | Subtask ID | Special Constraints | Score | | :--------: | :-----------------: | :---: | | $1$ | $N=5\times 10^5$, $Q=K-1$, Tree $1$ and Tree $2$ are exactly the same, including edge weights | $10$ | | $2$ | $N=5\times 10^5$, $Q=2K-2$ | $25$ | | $3$ | $N=5\times 10^5$, $K=200$, $Q=K-1$ | $19$ | | $4$ | $N=10^6$, $K=10^3$, $Q=K-1$ | $22$ | ### Interaction Example | Sample Output | Sample Input | | :-----------: | :----------: | | | `9 3 2 3` | | | `2 -1 2 1 1 5 1 4 5` | | | `9 4 5 5 7 3 -1 3 7` | | `1 5 7` | | | `? 1 5` | | | `? 1 7` | | | `!` | | | | `0 2 5 3` | | | `0 3 5 0` | | | `1 7` | | | `7 5` | | | `5 1` | | `3 5` | | | `5 3` | | | `2 8` | |  Translated by ChatGPT 5