Menji，我们想你！ - 题目

这是一个交互式问题。

Menji 迷路了，大家都很想念他。你的任务是找到他！

有一棵由 $n$ 个节点组成的二叉树 $T$，树 $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, \dots, 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$。

要报告答案，请按以下格式打印单行：

对于每个测试用例，你最多可以发送 $40$ 次信号。报告答案不计入发送信号的次数。

如果你发送了超过 $40$ 次信号，或者你发送的信号格式错误，或者你报告的答案不正确，交互将立即结束，你将获得 Wrong answer 的评测结果。

请注意，交互器是自适应的（adaptive），这意味着只要与约束条件以及之前查询的回答保持一致，答案可能会根据你的查询而改变。

保证所有测试用例的 $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

QOJ.ac