CF1061F Lost Root
题目描述
如果一个图是连通的且没有环，则称其为树。假设树以某个顶点为根，则当树满足每个节点要么是叶子节点（没有子节点），要么恰好有 $k$ 个子节点，并且所有叶子节点的深度都相同，则称其为完美 $k$ 叉树。
例如，下图展示了一个有 $15$ 个节点的完美二叉树：
现在有一棵包含 $n$ 个节点的完美 $k$ 叉树。节点被标记为 $1$ 到 $n$ 的不同整数，但你并不知道每个节点的具体标号。你需要找出树的根节点的标号。
你最多可以进行 $60 \cdot n$ 次如下类型的询问：
- "? $a$ $b$ $c$"：如果标号为 $b$ 的节点在从 $a$ 到 $c$ 的路径上，则返回 "Yes"，否则返回 "No"。
注意，$a$ 和 $c$ 本身也被认为在从 $a$ 到 $c$ 的路径上。
当你准备好报告树的根节点时，输出
- "! $s$"，其中 $s$ 是树根节点的标号。
你只能报告一次根节点，且该操作不计入 $60 \cdot n$ 次询问的限制。
输入格式
标准输入的第一行包含两个整数 $n$ 和 $k$（$3 \le n \le 1500$，$2 \le k < n$），分别表示树的节点数和 $k$ 的值。
保证 $n$ 一定能构成某个深度的完美 $k$ 叉树。
你最多可以进行 $60 \cdot n$ 次询问。每次询问，输出一行 "? $a$ $b$ $c$"，其中 $1 \le a, b, c \le n$。随后你需要读取一行，内容为 "Yes" 或 "No"，表示该询问的答案。
对于每个测试用例，树的结构是固定的，并且与你的询问无关。
当你准备好输出答案时，输出一行 "! $s$"，其中 $s$ 是根节点的标号，然后终止程序。
每次输出询问后不要忘记输出换行并刷新输出缓冲区，否则可能会因“空闲时间超限”而被判为超时。具体操作如下：
- C++：fflush(stdout) 或 cout.flush()
- Java：System.out.flush()
- Pascal：flush(output)
- Python：stdout.flush()
- 其他语言请参考相关文档
如果你的程序询问次数超过 $60 \cdot n$，即使其它交互流程正确，也会被判为“Wrong Answer”。
输出格式
见输入格式说明。
说明/提示
示例中的树如下：
示例输入输出展示了该测试的可能交互过程（空行仅为便于阅读）。
对应该示例的 hack 格式如下：
`
3 2
2 3 1
` # 额外说明 我们称如下顺序为树的“自然顺序”：首先是树的根节点，然后是所有深度为 $1$ 的节点（从左到右），接着是所有深度为 $2$ 的节点（从左到右），依此类推，直到最大深度。 因此，hack 数据中的 $a_1$ 就是根节点的标号。 由 ChatGPT 4.1 翻译
3 2
2 3 1
` # 额外说明 我们称如下顺序为树的“自然顺序”：首先是树的根节点，然后是所有深度为 $1$ 的节点（从左到右），接着是所有深度为 $2$ 的节点（从左到右），依此类推，直到最大深度。 因此，hack 数据中的 $a_1$ 就是根节点的标号。 由 ChatGPT 4.1 翻译