CF1990E2.Catch the Mole(Hard Version)

这是该问题的困难版本，唯一的区别在于查询次数的限制。

这是一个交互式问题。

给定一棵有 $n$ 个节点的树，节点 $1$ 为根节点。

有一只“鼹鼠”藏在某个节点上。为了找到它的位置，你可以选择一个整数 $x$（$1 \le x \le n$）向评测机发起一次询问。接下来，评测机会返回 $1$，如果鼹鼠在以 $x$ 为根的子树中；否则，评测机会返回 $0$。如果评测机返回 $0$ 且鼹鼠当前不在根节点 $1$，那么鼹鼠会移动到它当前所在节点的父节点。

请在最多 $160$ 次操作内，找出鼹鼠当前所在的节点。

每个测试包含多组测试用例。第一行包含测试用例数 $t$（$1 \le t \le 100$）。接下来是每组测试用例的描述。

每组测试用例的第一行包含一个整数 $n$（$2 \le n \le 5000$）。

接下来的 $n-1$ 行描述树的边。每行包含两个用空格分隔的整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$），表示节点 $u_i$ 和 $v_i$ 之间有一条边。

保证输入数据构成一棵树。

本题的交互器是非自适应的。也就是说，鼹鼠最初所在的节点在每个测试用例中是固定的，在交互过程中不会改变。

你可以选择一个顶点 $x$（$1 \le x \le n$）进行一次询问，输出如下格式的一行：

• "? x"

之后，你会收到：

• $0$，如果鼹鼠不在以 $x$ 为根的子树中；
• $1$，如果鼹鼠在以 $x$ 为根的子树中。

每个测试用例最多可以进行 $160$ 次此类询问。

接下来，如果你的程序已经找到了鼹鼠当前所在的节点，输出如下格式的一行：

• "! x"

注意，这一行不计入查询次数。

输出每次查询或每组测试用例的答案后，不要忘记输出换行并刷新输出缓冲区。否则会收到 Idleness Limit Exceeded 的判定。具体操作如下：

• C++：fflush(stdout) 或 cout.flush()
• Java：System.out.flush()
• Pascal：flush(output)
• Python：stdout.flush()
• 其他语言请参考相关文档。

Hack 数据

Hack 时请按照如下格式：

第一行包含测试用例数 $t$（$1 \le t \le 100$）。接下来是每组测试用例的描述。

每组测试用例的第一行包含两个整数 $n$ 和 $x$（$2 \le n \le 5000$，$1 \le x \le n$），分别表示树的大小和鼹鼠的初始位置。

接下来的 $n-1$ 行描述树的边。每行包含两个用空格分隔的整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$），表示节点 $u_i$ 和 $v_i$ 之间有一条边。

输入数据必须构成一棵树。

在第一个测试用例中，鼹鼠最初在节点 $2$。

对于查询 "? 2"，评测机返回 $1$，因为鼹鼠在以 $2$ 为根的子树中。此时鼹鼠不会移动。

答案 $2$ 即为鼹鼠当前所在的节点，因此答案是正确的。

在第二个测试用例中，鼹鼠最初在节点 $6$。

对于查询 "? 2"，评测机返回 $0$，因为鼹鼠不在以 $2$ 为根的子树中。此时鼹鼠从节点 $6$ 移动到节点 $5$。

对于查询 "? 6"，评测机返回 $0$，因为鼹鼠不在以 $6$ 为根的子树中。此时鼹鼠从节点 $5$ 移动到节点 $4$。

对于查询 "? 4"，评测机返回 $1$，因为鼹鼠在以 $4$ 为根的子树中。此时鼹鼠不会移动。

答案 $4$ 即为鼹鼠当前所在的节点，因此答案是正确的。

请注意，示例仅用于帮助理解题意，示例中的查询并不保证能唯一确定鼹鼠的位置。

由 ChatGPT 4.1 翻译