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 翻译