这是一个交互问题。
当小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$$$