← 返回题目列表

Codeforces · 1990/E1

E1. 捉地鼠(简单版)

中文机器翻译题面 查看原题

这是问题的简单版本。唯一的区别是查询数量的限制。

这是一个交互问题。

给您一棵由 $$$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$$$是痣所在的当前节点,所以答案被认为是正确的。

请注意,该示例仅用于理解该语句,示例中的查询不能保证确定痣的唯一位置。