这是问题的简单版本。唯一的区别是查询数量的限制。
这是一个交互问题。
给您一棵由 $$$n$$$ 节点组成的树,其中节点 $$$1$$$ 作为根节点。
其中一个节点中有一颗隐藏的痣。要找到它的位置,你可以选择一个整数$$$x$$$ ($$$1 \le x \le n$$$) 向陪审团询问。接下来,当鼹鼠位于子树 $$$x$$$ 中时,陪审团将返回 $$$1$$$。否则,法官将返回$$$0$$$。如果判断返回$$$0$$$并且地鼠不在根节点$$$1$$$,则地鼠会移动到它当前所在节点的父节点。
最多使用 $$$300$$$ 操作来查找摩尔所在的当前节点。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$ 中。
对于每个测试用例,您最多可以进行 $$$300$$$ 这种形式的查询。
接下来,如果你的程序找到了摩尔所在的当前节点,则打印以下形式的行:
- “!x”
请注意,此行不被视为查询,并且在计算所请求的查询数时不会被考虑在内。
此后,继续下一个测试用例。
如果您在交互过程中进行超过 $$$300$$$ 查询,您的程序必须立即终止,并且您将收到错误答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。
打印测试用例的查询或答案后,不要忘记输出行尾并刷新输出。否则,您将得到 Idleness Limit Exceeded 的判决。为此,请使用:
- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。
黑客
要破解,请遵循以下测试格式。
第一行包含测试用例的数量 $$$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$$$ 之间的边。
输入数据必须表示一棵树。
示例
输入 #1
2 2 1 2 1 6 1 2 1 3 1 4 4 5 5 6 0 0 1
输出 #1
? 2 ! 2 ? 2 ? 6 ? 4 ! 4
注意
在第一个测试用例中,鼹鼠最初位于节点 $$$2$$$ 中。
对于查询“? 2”,陪审团返回 $$$1$$$,因为鼹鼠位于子树 $$$2$$$ 中。问完之后,鼹鼠就不动了。
答案$$$2$$$是痣所在的当前节点,所以答案被认为是正确的。
在第二个测试用例中,鼹鼠最初位于节点 $$$6$$$ 中。
对于查询“? 2”,陪审团返回 $$$0$$$,因为鼹鼠不在子树 $$$2$$$ 中。执行此查询后,鼹鼠从节点 $$$6$$$ 移动到节点 $$$5$$$。
对于查询“? 6”,陪审团返回 $$$0$$$,因为鼹鼠不在子树 $$$6$$$ 中。执行此查询后,鼹鼠从节点 $$$5$$$ 移动到节点 $$$4$$$。
对于查询“? 4”,陪审团返回 $$$1$$$,因为鼹鼠位于子树 $$$4$$$ 中。问完之后,鼹鼠就不动了。
答案$$$4$$$是痣所在的当前节点,所以答案被认为是正确的。
请注意,该示例仅用于理解该语句,示例中的查询不能保证确定痣的唯一位置。