← 返回题目列表

Codeforces · 2193/G

G. 树中的路径

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

这是一个交互问题.

在这个交互式问题中,给定一个由 $$$n$$$ 个顶点组成的非循环、连通、无向图。我们将两个顶点 $$$v$$$ 和 $$$u$$$ 之间的路径定义为以下序列 不同 上面写着 顶点 $$$p_1, p_2,\dots p_k$$$ 使得 $$$p_1 = v$$$, $$$p_k = u$$$, 并且对于所有 $$$i$$$ ($$$1 \le i \lt k$$$), 顶点 $$$p_i$$$ 和$$$p_{i+1}$$$。

有隐藏顶点 $$$x$$$ 和 $$$y$$$ (它们可能重合)。您可以进行以下查询:

  • 选择两个顶点 $$$a$$$, $$$b$$$ ($$$1\le a, b\le n$$$)。如果顶点 $$$x$$$、$$$y$$$ 之间的路径与顶点 $$$a$$$、$$$b$$$ 之间的路径共享至少一个公共顶点,则评审团将响应 $$$1$$$,否则将响应 $$$0$$$。
您的任务是在不超过 $$$\lfloor\frac{n}{2}\rfloor + 1$$$ 查询中找到 $$$x$$$ 和 $$$y$$$ 之间路径上的至少一个顶点。

请注意,交互器是 自适应,这意味着隐藏的顶点可能会根据您的查询而变化,但不会与之前的查询相矛盾。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1\le t\le 10^4$$$) — 测试用例的数量。以下几行描述了测试用例。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — 图中的顶点数。

接下来有 ​​$$$n - 1$$$ 行,每行包含两个整数 $$$v$$$、$$$u$$$ ($$$1\le v, u\le n$$$),表示顶点 $$$v$$$ 和 $$$u$$$ 通过图中的边连接。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

互动

要查找路径上的任何顶点,您最多可以使用 $$$\lfloor\frac{n}{2}\rfloor + 1$$$ 查询。为此,请使用“? $$$a$$$ $$$b$$$”形式的查询。

每次查询后,读取一个数字,$$$0$$$ 或 $$$1$$$ — 对查询的响应。

当找到所需顶点之一时,按以下格式输出一行:“! $$$v$$$” ($$$1\le v\le n$$$),其中 $$$v$$$ 是您找到的顶点。

如果您的程序对一个测试用例进行了超过 $$$\lfloor\frac{n}{2}\rfloor + 1$$$ 查询,则 对查询的答复将 为 $$$-1$$$,收到这样的响应后,您的程序应立即终止以接收以下判决 错误答案。否则,它可能会收到任何其他判决。

输出查询后,不要忘记输出换行符并刷新输出缓冲区。否则,您将收到以下判决: 解决方案“超时”。要刷新缓冲区,请使用:

  • $$$\tt{fflush(stdout)}$$$ 或 $$$\tt{cout.flush()}$$$ 在 C++ 中;
  • $$$\tt{System.out.flush()}$$$ 在 Java 中;
  • $$$\tt{flush(输出)}$$$(帕斯卡);
  • $$$\tt{stdout.flush()}$$$ 在 Python 中;
  • 请参阅其他语言的文档。

示例

输入
复制

3

2
1 2

1


3
1 2
1 3

0

0


4
1 2
2 3
2 4

0

1

输出
复制

? 1 1

! 1


? 1 1

? 2 2

! 3


? 1 3

? 4 4

! 4