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

试题来自 [清华大学学生算法协会](https://gitlink.org.cn/thusaa/ICPC2025shanghai)。

Menji 走丢了，大家都很想念他。你的任务就是找到他！ 有一棵**二叉**树 $T$，由 $n$ 个顶点构成，树 $T$ 的每条边长度均为 $1$。Menji 藏在顶点 $X$ 处。你知道树的结构，但不知道 $X$。 为了找到 $X$，你可以发送信号。你可以选定一个顶点 $u$ 并选定一个信号强度 $k$，然后从顶点 $u$ 发送强度为 $k$ 的信号。如果 $u$ 和 $X$ 之间的距离不超过 $k$，Menji 就会收到信号并发回一个信号，你也将收到信号。否则，你将收不到任何东西。 发送信号很慢，而你又很着急，所以请用不超过 $40$ 次信号确定 Menji 的位置。 ### 交互协议 输入包含多组测试用例。第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。 对于每个测试用例，第一行包含一个整数 $n$ ($2 \le n \le 3 \times 10^4$)，表示树中的顶点数。 第二行包含 $n - 1$ 个整数 $fa_2, fa_3, \cdots, fa_n$ ($1 \le fa_i < i$)，其中 $fa_i$ 是顶点 $i$ 在树上的父节点。树以顶点 $1$ 为根。 保证这棵树是一棵二叉树，即不存在 $1 < i < j < k \le n$ 使得 $fa_i = fa_j = fa_k$。 发送信号时，请按以下格式输出一行： - `? u k`：表示你在顶点 $u$ 处生成一个强度为 $k$ 的信号。你需要保证 $1 \le u \le n$，$0 \le k \le n$。然后你必须读入一个整数 $o$ ($o \in \{0,1\}$)。如果你收到了信号，或者说 $dis(u, X) \le k$，则 $o = 1$，否则 $o = 0$。 报告答案时，请按以下格式输出一行： - `! u`：表示你已经找到 $X = u$。输出此行后，你需要进入下一个测试用例，如果没有更多测试用例则终止程序。 对于每个测试用例，你最多可以发送 $40$ 次信号。报告答案不计入信号次数。 如果你发送了超过 $40$ 次信号，或者发送的信号格式错误，或者报告的答案不正确，交互将会终止，你将得到 `Wrong answer` 的判定。 注意，交互器是**自适应的**，这意味着答案可能会根据你的询问而改变，只要它始终与约束条件和先前询问的回答保持一致即可。 保证所有测试用例的 $n$ 之和不超过 $3 \times 10^4$。 在打印每一行后，请不要忘记输出换行符并刷新输出。在 C++ 中你可以使用 `fflush(stdout)` 或 `cout.flush()` 来刷新流，Java 中使用 `System.out.flush()`，Python 中使用 `stdout.flush()`。

无

无

翻译由 DeepSeek V4 Pro 完成