← 返回题目列表

Codeforces · 1534/H

H. 丢失节点

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

这是一个交互问题。

当小Ericyi今年获得IOI资格时,他所有的朋友都给了他一份礼物:一棵$$$n$$$节点树!

在飞往 IOI 的航班上,小 Ericyi 非常无聊,所以他决定用他的新树和 Little Yvonne 玩一个游戏。首先,小伊冯在树上选择两个(不一定不同)节点$$$a$$$和$$$b$$$(没有告诉Ericyi),然后给他一个提示$$$f$$$(这是从$$$a$$$到$$$b$$$路径上的某个节点)。

然后,小Ericyi就可以反复问以下问题:

- 如果我将树植根于节点 $$$r$$$ (Ericyi 选择 $$$r$$$),那么 $$$a$$$ 和 $$$b$$$ 的最低共同祖先是什么?

小Ericyi的目标是找到节点$$$a$$$和$$$b$$$,并将它们报告给小Yvonne。

不过,小Yvonne认为这个游戏太简单了,所以在给小Ericyi提示$$$f$$$之前,他也希望小Ericyi在$$$a$$$、$$$b$$$和$$$f$$$的所有可能性中,假设小Ericyi处于最佳状态,首先找到确定$$$a$$$和$$$b$$$所需的最大查询次数。 Little Ericyi 将最佳策略定义为进行最少查询次数的策略。当然,一旦小艾里奇回复了最大数量的查询,小伊冯就只会让他在游戏中使用那么多的查询。

树、$$$a$$$、$$$b$$$ 和 $$$f$$$ 在游戏开始前都是固定的,并且不会随着查询的进行而改变。

互动

首先读取包含整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) 的行,即树中的节点数。

接下来的 $$$n−1$$$ 行描述了 Little Ericyi 的树。这些行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u,v \le n$$$) 表示 $$$u$$$ 和 $$$v$$$ ($$$u \neq v$$$) 之间的边。保证这些边形成一棵树。

之后,您应该输出 $$$k$$$,即假设 Little Ericyi 发挥最佳状态,在 $$$a$$$、$$$b$$$ 和 $$$f$$$ 的所有可能性中确定 $$$a$$$ 和 $$$b$$$ 所需的最大查询数。您应该输出行尾并在打印 $$$k$$$ 后刷新输出。

之后读取包含整数 $$$f$$$ ($$$1 \le f \le n$$$) 的行 - 提示:从 $$$a$$$ 到 $$$b$$$(含)的路径上的节点。

之后就可以开始查询了。您最多只能进行 $$$k$$$ 查询,其中 $$$k$$$ 是您打印的数字。

每个查询均以“? r”格式进行,其中 $$$r$$$ 是整数 $$$1 \le r \le n$$$ 表示您想要查询的根节点。

然后,您将收到一个整数 $$$x$$$ ($$$1 \le x \le n$$$),即 $$$a$$$ 和 $$$b$$$ 的最低共同祖先(如果树的根位于 $$$r$$$)。

当您的程序找到节点 $$$a$$$、$$$b$$$ 时,请按以下格式报告答案:“! a b”,其中 $$$a$$$ 和 $$$b$$$ 是两个隐藏节点,并在刷新输出流后立即正常终止您的程序。您可以按任意顺序输出 $$$a$$$ 和 $$$b$$$。

打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

如果您在任何时候做出无效输出或进行超过 $$$k$$$ 查询,则交互将终止,并且您将收到错误答案判决。无效输出定义为无效查询或 $$$k$$$ 值小于 $$$0$$$ 或大于 $$$n$$$。

黑客

要破解解决方案,请使用以下格式:

第一行包含整数 $$$n$$$ ($$$1 \le n \le 10^5$$$)。

接下来的 $$$n−1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u,v \le n$$$) 表示 $$$u$$$ 和 $$$v$$$ ($$$u \neq v$$$) 之间的边。这些 $$$n-1$$$ 边必须形成一棵树。

输入的下一行包含节点 $$$a$$$ 和 $$$b$$$ ($$$1 \le a,b \le n$$$),以空格分隔。

输入的最后一行包含整数 $$$f$$$ ($$$1 \le f \le n$$$)。节点 $$$f$$$ 应该位于从 $$$a$$$ 到 $$$b$$$ (含)的简单路径上。

示例

输入 #1

4
3 2
2 1
2 4

1

1

2

2

输出 #1

3

? 1

? 2

? 3

! 4 1

输入 #2

5
3 1
1 4
4 5
4 2

1

4

1

4

输出 #2

3

? 4

? 1

? 5

! 1 4

注意

这是第一个示例交互中的树。节点 $$$a$$$ 和 $$$b$$$ 突出显示。

请注意,$$$a$$$ 和 $$$b$$$ 可以按任何顺序输出。

此外,为了方便起见,以下是查询每个节点 $$$1,2,\ldots,n$$$ 的答案:

- $$$1$$$: $$$1$$$
- $$$2$$$: $$$2$$$
- $$$3$$$: $$$2$$$
- $$$4$$$: $$$4$$$

__________________________________________

这是第二个示例交互中的树。节点 $$$a$$$ 和 $$$b$$$ 再次突出显示。

最后,为方便起见,以下是查询每个节点 $$$1,2,\ldots,n$$$(例如 $$$2$$$)的答案:

- $$$1$$$: $$$1$$$
- $$$2$$$: $$$4$$$
- $$$3$$$: $$$1$$$
- $$$4$$$: $$$4$$$
- $$$5$$$: $$$4$$$