← 返回题目列表

Codeforces · 1174/F

F. Ehab 和大结局

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

这是一个交互问题。

给你一棵由 $$$n$$$ 节点组成的树,根节点为 $$$1$$$。树是一个没有环的连通图。

我们选择了一个隐藏节点$$$x$$$。为了找到该节点,您可以提出两种类型的查询:

- d $$$u$$$ ($$$1 \le u \le n$$$)。我们将用节点 $$$u$$$ 和 $$$x$$$ 之间的距离来回答。两个节点之间的距离是它们之间的最短路径中的边数。
- s $$$u$$$ ($$$1 \le u \le n$$$)。我们将回答从 $$$u$$$ 到 $$$x$$$ 路径上的第二个节点。然而,情节出现了转折。如果 $$$u$$$ 不是 $$$x$$$ 的祖先,您将收到“错误答案”的判决!

如果 $$$a \ne b$$$ 且从节点 $$$1$$$ 到节点 $$$b$$$ 的最短路径经过节点 $$$a$$$,则节点 $$$a$$$ 称为节点 $$$b$$$ 的祖先。请注意,在这个问题中,节点不是其自身的祖先。

您能在不超过 $$$36$$$ 查询中找到 $$$x$$$ 吗?隐藏节点在每次测试中都是预先固定的,不依赖于您的查询。

输入

第一行包含整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 树中的节点数。

接下来的 $$$n-1$$$ 行包含两个空格分隔的整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u,v \le n$$$),这意味着节点 $$$u$$$ 和 $$$v$$$ 之间有一条边。保证给定的图是一棵树。

互动

要提出问题,请以上述格式之一打印:

- d $$$u$$$ ($$$1 \le u \le n$$$),或
- s $$$u$$$ ($$$1 \le u \le n$$$)。

在每个问题之后,您应该阅读答案:距离或路径上的第二个顶点,如图例中所述。

如果我们回答 $$$-1$$$ 而不是有效答案,则意味着您超出了查询数量、进行了无效查询或违反了第二类查询中的条件。收到$$$-1$$$后立即退出,您将看到错误的答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

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

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

黑客:

第一行应包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le x \le n$$$)。

接下来的 $$$n-1$$$ 行应包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u,v \le n$$$),这意味着节点 $$$u$$$ 和 $$$v$$$ 之间有一条边。边缘必须形成一棵树。

输出

要打印答案,请打印“!x”(不带引号)。

示例

输入 #1

5
1 2
1 3
3 4
3 5
3
5

输出 #1

d 2
s 3
! 5

注意

在第一个示例中,隐藏节点是节点 $$$5$$$。

我们首先询问节点 $$$x$$$ 和节点 $$$2$$$ 之间的距离。答案是 $$$3$$$,因此节点 $$$x$$$ 要么是 $$$4$$$ 要么是 $$$5$$$。然后我们询问从节点 $$$3$$$ 到节点 $$$x$$$ 的路径中的第二个节点。请注意,节点 $$$3$$$ 是节点 $$$5$$$ 的祖先。我们收到节点 $$$5$$$ 作为答案。最后,我们报告隐藏节点是节点$$$5$$$。