背景

试题来自 清华大学学生算法协会。

题目描述

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()。

2
7
1 1 2 2 3 3

1

0

0

7
1 1 2 2 3 3

0

1

? 2 1

? 3 2

? 4 0

! 5


? 2 1

? 3 0

! 3

提示

翻译由 DeepSeek V4 Pro 完成