P10553 [ICPC 2024 Xi'an I] Guess The Tree

有一个满二叉树，具有 $n$ 层（因此它恰好有 $2^n-1$ 个节点）。每个节点都有一个从 $1$ 到 $2^n-1$ 的整数 ID，这 $2^n-1$ 个 ID 形成一个从 $1$ 到 $2^n-1$ 的排列，但你并不知道具体的排列。 你需要通过最多 $4800$ 次查询找到这 $2^n-1$ 个节点的 ID。

第一行包含一个整数 $n(1\leq n\leq 10)$，表示满二叉树的层数。 为了进行一次查询，你需要选择两个节点，其 ID 为 $u,v(1\leq u,v\leq 2^n-1)$，并输出如下格式的一行： > "? u v" 之后，你将收到： > "t" 即 $u$ 和 $v$ 的最近公共祖先的 ID。 你最多可以进行 $4800$ 次查询。 如果你已经找到了树的结构，输出如下格式的一行： "! $f_1\ f_2\ f_3\ f_4$ ... $f_{2^n-1}$" 其中 $f_i$ 表示第 $i$ 个节点的父节点的 ID。如果没有父节点，则 $f_i=-1$。 在打印查询或测试用例的答案后，不要忘记输出行尾并刷新输出。否则，你将得到「Idleness Limit Exceeded」的判定。为此，请使用： `fflush(stdout)` 或 `cout.flush()` 在 C++ 中； `System.out.flush()` 在 Java 中； `stdout.flush()` 在 Python 中。 此任务中的交互器不是自适应的。

无

在这个例子中，树的根是 $3$，它的两个儿子是 $1$ 和 $2$。 对于任何查询 "? a b"，如果 $a eq b$，评测系统将返回答案 $3$。 因此我们找到了树的根是 $3$。（由 ChatGPT 4o 翻译）