P14762 [Opoi 2025] CCD 的长恨歌

~~前几天~~ 一年前 CCD 因为模拟赛挂分而被 \_Eriri\_ 嘲讽，于是他准备出一道题来嘲讽 \_Eriri\_。 > 栋皇重色思倾国，御宇多年求不得。 > > 蒋家有女初长成，养在深闺人未识。 > > 天生丽质难自弃，一朝选在君王侧。 > > 回眸一笑百媚生，六宫粉黛无颜色。 [upd 2025/5/5].

**请注意，此题仅支持 C++11 及以上提交！** 栋明皇有一棵非常神秘的有 $n$ 个点的有根树 $T$，根为 $1$。 而你，作为尊贵的蒋贵妃，非常想知道树 $T$ 的形态，但你每次只能向栋明皇问一个二元组 $(i,j)\ (1 \le i , j \le n)$，栋明皇会告诉你这两个点在树上的最近公共祖先 $k$。由于栋明皇还要忙着筹备 Opoi，他只允许你向他问 $n \times 300$ 次问题。 幸运的是，栋明皇喜欢紧凑的结构，所以这颗树的**叶子个数至多为 $20$**。 本题是一道交互题。 提交时，请在程序中加入以下函数声明语句： ```cpp int LCA(int,int); ``` 这使你可以调用 `LCA(x,y)` 并得到它们的 LCA。 你不需要，也不应该实现主函数，你只需要实现下列函数： ```cpp vector guess(int n); ``` - 每个测试点交互库只会调用一次该函数。 - 其中 $n$ 表示本次猜测的树 $T$ 的结点个数。 - 返回的 vector 描述了树 $T$ 的结构，其中 `vector` 的每一个 `pair` 表示树的一条边 $(u,v)$，每条边两个节点的顺序和边与边之间的顺序没有要求。 - 单次 `LCA(x, y)` 复杂度是严格 $O(1)$ 的，交互库预处理复杂度 $O(n \log_2 n)$。 - **SPJ 不会因你 LCA 的调用次数过多返回 `WA`，但如果超过了 $n \times 300$ 次，那么后面的 LCA 调用结果都是 `-1`。** 题目附件里有一个示范模板 `template.cpp`，使用它你可以获得 $0$ 分的好成绩。

无

无

### 样例解释 | You | Interactor | | :----------: | :----------: | | `LCA(1,2)` | `1` | | `1 2` | Accepted | 除了样例输出，输出 `2 1` 也是一个合法的解。 --- ### 数据范围与约定 对于 $100\%$ 的数据，$1 \le n \le 2 \times 10^4$。 **部分分：数据共有 $20$ 组，对于第 $i$ 组数据，保证树的叶子个数至多为 $i$。** --- ### 提示 如果你不知道怎么解决交互题，可以参考[这题](P1947)。 本题模板程序与模板交互库见附件中的 `template.cpp` 与 `s_interactor.cpp`。