P17121 [ICPC 2025 Shanghai R] Menji, we miss you!

Menji is lost and everyone misses him. It’s your job to find him! There is a **binary** tree $T$, consisting of $n$ vertices, and each edge of tree $T$ is of length $1$. Menji is hiding at vertex $X$. You know the structure of the tree. However, you don’t know $X$. To find $X$, you can send signals. You can select a vertex $u$ and select a signal strength $k$, then send a signal of strength $k$ from vertex $u$. If the distance between $u$ and $X$ is no more than $k$, Menji will receive the signal and send a signal back, and you will receive the signal. Otherwise, you won’t receive anything. Sending signals is slow, and you are in a hurry, so please determine the position of Menji in no more than $40$ signals. ### Interaction Protocol The input contains multiple testcases. The first line of the input contains an integer $T$ ($1 \le T \le 100$), the number of testcases. For each testcase, the first line contains an integer $n$ ($2 \le n \le 3 \times 10^4$), the number of vertices in the tree. The second line contains $n - 1$ integers $fa_2, fa_3, \cdots, fa_n$ ($1 \le fa_i < i$), where $fa_i$ is the parent of $i$ on the tree. The tree is rooted at vertex $1$. It is guaranteed that the tree is a binary tree, that is, there doesn’t exist $1 < i < j < k \le n$, such that $fa_i = fa_j = fa_k$. To send a signal, print a single line in the following format: - $? \ u \ k$: Indicate that you create a signal at vertex $u$ with strength $k$. You need to ensure $1 \le u \le n, 0 \le k \le n$. Then you have to read an integer $o$ ($o \in \{0,1\}$). If you received the signal, or equivalently, $dis(u,X) \le k$, then $o = 1$, otherwise $o = 0$. To report the answer, print a single line in the following format: - $! \ u$: Indicate that you have found $X = u$. You need to move on to the next testcase after printing this, or terminate if there’s no more. For each testcase, you can send at most $40$ signals. Reporting the answer does not count as sending a signal. If you send more than $40$ signals, or the signal you sent is malformed, or the answer you reported is incorrect, then the interaction will end and you will receive `Wrong answer` verdict. Note that the interactor is **adaptive**, meaning that the answer may change depending on your queries as long as it remains consistent with the constraints and the answers to the previous queries. It’s guaranteed that the sum of $n$ over all testcases does not exceed $3 \times 10^4$. After printing each line do not forget to output the end of line and flush the output. You may use `fflush(stdout)` or `cout.flush()` to flush the stream for $C++$, use `System.out.flush()` for Java and `stdout.flush()` for Python.

N/A

N/A