P12447 [COTS 2025] 砍树 / Stablo

**这是一道交互题。本题中，交互库是非自适应的。** 有一棵 $N$ 个节点的树。这棵树中，每个节点度数至多为 $3$。 你可以提问至多 $K=2.5\times 10^5$ 次。每次给定三个两两不同的节点 $a,b,c$，交互库会回答： - $\text{0}$，如果 $\operatorname{dist}(a,b)=\operatorname{dist}(a,c)$; - $\text{1}$，如果 $\operatorname{dist}(a,b)\lt\operatorname{dist}(a,c)$; - $\text{2}$，如果 $\operatorname{dist}(a,b)\gt\operatorname{dist}(a,c)$。 定义 $\operatorname{dist}(u,v)$ 表示 $u,v$ 最短路上边的数量。 试通过询问还原这棵树。 虽然你可以提问 $K=2.5\times 10^5$ 次，但是想要获得更高的分数，需要更少的询问次数。见「计分方式」。 ### 实现细节 首先读入正整数 $N$。读入后发起询问： - $\texttt{?}$ $a$ $b$ $c$：发起一次询问。 - 你需要保证 $1 \leq a, b, c \leq N$ 且 $a \neq b$，$b \neq c$，$c \neq a$。 - **最多可以询问 $2.5\times 10^5$ 次。** - 从标准输入流读入一个整数表示答案，具体见「题目描述」。 - $\texttt{!}$：报告答案。 - 输出 $\texttt{!}$ 后，接下来再输出 $(N-1)$ 行，每行两个正整数，描述一条树边。 - 你可以以任意顺序输出这 $(N-1)$ 条边。 - 报告答案后，你的程序必须终止运行。 **每次提问后，都需要换行并刷新缓冲区。** **交互库是非自适应的**。也就是说，树的形态在交互开始前已经固定。

无

无

### 样例解释 样例中，树边有 $\{(1,2),(2,3),(3,4)\}$。 ### 数据范围 - $N\lt 512$； - 每个节点度数至多为 $3$。 ### 子任务 - $\text{Subtask 0 (0 pts)}$：样例。 - $\text{Subtask 1 (10 pts)}$：每个节点度数至多为 $2$。 - $\text{Subtask 2 (20 pts)}$：树是满二叉树。 - 换句话说，树是完全二叉树，且存在正整数 $k$ 使得 $N=2^k-1$。 - $\text{Subtask 3 (70 pts)}$：无额外限制。 ### 计分方式 答案错误，询问次数超限，或者出现了任何未能成功运行结束的情况，得 $0$ 分。 假设你在某个分值为 $B$ 的子任务中至多用了 $K$ 次查询，则子任务得分为 $$\min\left(1, \left(\frac{14000}{K}\right)^{0.7}\right) \cdot B$$ **交互库是非自适应的**。也就是说，树的形态在交互开始前已经固定。