CF1990E1 Catch the Mole(Easy Version)

题目描述

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

这是一个交互式问题。

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

有一只“鼹鼠”藏在某个节点上。你可以通过选择一个整数 $x$（$1 \le x \le n$）向评测机发起一次询问。接下来，评测机会返回 $1$，如果鼹鼠在以 $x$ 为根的子树内；否则，评测机会返回 $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$ 次查询，你的程序必须立即终止，否则会收到 Wrong Answer 判定。否则，如果你的程序继续从已关闭的流中读取数据，可能会收到任意判定。

每次输出查询或输出答案后，别忘了输出换行并刷新输出缓冲区，否则会收到 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$ 之间有一条边。

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

输入输出样例 #1

输入 #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$ 即为鼹鼠当前所在的节点，因此答案是正确的。

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

由 ChatGPT 4.1 翻译