「Codeforces 1174F」Ehab and the Big Finale
题目链接:Codeforces 1174F
这是一道交互题。
给定一棵有 $n$ 个点的树,节点 $1$ 为根节点。
我们选择一个隐藏节点 $x$,你需要进行以下三种操作来找到这个节点 $x$ 的编号。
d u
:你会得到节点 $u$ 和 $x$ 之间的距离。两个节点之间的距离定义为最短路径上的边数。s u
:你会得到节点 $u$ 到 $x$ 的最短路径上的第二个节点。但是如果 $u$ 不是 $x$ 的祖先,你会直接得到Wrong answer
的结果!! u
:回答隐藏节点 $x$ 的编号为 $u$。
你需要在 $36$ 次询问(不包括回答)内找到 $x$ 的编号。这个隐藏节点 $x$ 不会根据你的询问而改变。
数据范围:$2 \le n \le 2 \times 10 ^ 5$。