CF1174F Ehab and the Big Finale

这是一个交互题。 给定一棵包含 $n$ 个节点的树，以节点 $1$ 作为根节点。树是一种无环连通图。 我们选择了一个隐藏节点 $x$。为了找到这个节点，你可以进行两种类型的询问： - d $u$（$1 \le u \le n$）。我们会回答节点 $u$ 与 $x$ 之间的距离。两个节点之间的距离是它们之间最短路径上的边数。 - s $u$（$1 \le u \le n$）。我们会回答从 $u$ 到 $x$ 的路径上的第二个节点。但是，这里有一个限制。如果 $u$ 不是 $x$ 的祖先，你会收到“Wrong answer”判定！ 如果节点 $a$ 是节点 $b$ 的祖先，意味着 $a \ne b$ 且从节点 $1$ 到节点 $b$ 的最短路径经过节点 $a$。注意，在本题中，一个节点不是自己的祖先。 你能否在不超过 $36$ 次询问内找到 $x$？隐藏节点在每个测试中是预先固定的，并且与你的询问无关。

第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示树的节点数。 接下来的 $n-1$ 行，每行包含两个用空格分隔的整数 $u$ 和 $v$（$1 \le u,v \le n$），表示在节点 $u$ 和 $v$ 之间有一条边。保证给定的图是一棵树。

要输出答案，请输出 "! x"（不带引号）。 交互说明 要进行询问，请按以下格式之一输出： - d $u$（$1 \le u \le n$），或 - s $u$（$1 \le u \le n$）。 每次询问后，你都应读取答案：要么是距离，要么是路径上的第二个节点，如题目描述所述。 如果我们返回 $-1$ 而不是有效答案，说明你超出了询问次数、进行了非法询问，或违反了第二种询问的条件。收到 $-1$ 后应立即退出，否则你的程序会因为继续读取已关闭的流而得到任意判定。 每次输出询问后，不要忘记输出换行并刷新输出缓冲区。否则，你会收到“Idleness limit exceeded”判定。具体做法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请参考相关文档。 Hack 数据格式： 第一行应包含两个整数 $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$ 之间有一条边。所有边必须构成一棵树。

在第一个样例中，隐藏节点是节点 $5$。  我们首先询问节点 $2$ 与 $x$ 之间的距离。答案是 $3$，所以 $x$ 可能是节点 $4$ 或 $5$。然后我们询问从节点 $3$ 到 $x$ 的路径上的第二个节点。注意这里节点 $3$ 是节点 $5$ 的祖先。我们收到节点 $5$ 作为答案。最后，我们报告隐藏节点是节点 $5$。 由 ChatGPT 4.1 翻译