P10539 [APIO2024] 魔术表演

在洛谷上提交时，只需要提交一个文件。 不要引入 `alice.h` 和 `bob.h`。在文件头加入以下内容： ```cpp long long setN(int n); ``` 只支持 C++17 / C++20 提交。

Alice 和 Bob 是著名的魔术师。Catherine 是一位富豪，她非常喜欢观看 Alice 和 Bob 的魔术。某一天，Catherine 决定向 Alice 和 Bob 发出挑战：只要他们能成功表演如下的魔术，Catherine 就将向他们提供巨额奖金！这个魔术的表演过程如下： - 步骤 $1$：Bob 进⼊⼀个密室中，在魔术的全程中，他只能与 Catherine 交流。接下来，Alice 告诉 Catherine ⼀个在 $2$ 到 $5000$ 之间的整数 $n$。 - 步骤 $2$：Catherine 告诉 Alice ⼀个在 $1$ 到 $10^{18}$ 之间的整数 $X$。 - 步骤 $3$：Alice 生成⼀个具有 $n$ 个节点的树，并告诉 Catherine。 - 步骤 $4$：Catherine 删除树中的⼀些边（至多 $\left\lfloor\dfrac{n-2}{2}\right\rfloor$ 条），并将剩余的边告诉 Bob。 - 步骤 $5$：Bob 根据 Catherine 给出的信息，猜出 Catherine 告诉 Alice 的数是多少。 然⽽，Alice 和 Bob 被这个魔术难倒了，于是他们不得不寻求你的帮助。请你写一段程序，实现 Alice 和 Bob 的策略，以帮助他们赢得 Catherine 的挑战。 通信方式： 你需要实现两个函数 1. `std::vector Alice();` - 对于每组测试数据，这个函数只会被调用⼀次。 - 函数应当返回⼀个含有 `pair` 类型的 `vector`，表示 Alice 在魔术的步骤 3 中生成的树的边集。 - 注意树中的节点应当从 1 开始编号。 - 你需要确保函数返回的树是符合规范的，也就是说，树中应当恰好包含 n − 1 条边，且所有节点彼此连通。 函数 `Alice()` 应当调用如下函数**恰好⼀次**： `long long setN(int n);` - 这个函数表示，在魔术的步骤 1 中，Alice 选择⼀个数 $n$ 告诉 Catherine。 - 函数返回⼀个数 $X$，表示 Catherine 在魔术的步骤 2 中告诉 Alice 的数。 --- 2. `long long Bob(std::vector V);` - 对于每组测试数据，这个函数只会被调用⼀次，且⼀定是在调用 `Alice()` 之后。 - $V$ 表⽰在魔术的步骤 4 中，Catherine 告诉 Bob 的边集。 - 上述边集是有序的，具体而言： - 对于⼀条边的两个端点而言，编号较⼩的端点靠前； - 所有的边按照第⼀个端点为第⼀关键字、第⼆个端点为第⼆关键字的顺序升序排序。 - 函数应当返回⼀个整数 $X$，表⽰ Bob 在魔术的步骤 5 中给出的回答。

无

无

### 例子 考虑下面的调用： 调用函数| 返回值 :-:|:-: `Alice()`| `setN(4)`| $3$ ||$\{\{1, 2\}, \{2, 3\}, \{2, 4\}\}$ `Bob({{1,2},{2,4}})`| $3$ 该样例代表了以下场景： - 步骤 1：最开始，Alice 将数字 $4$ 告诉 Catherine。 - 步骤 2：Catherine 将数字 $3$ 告诉 Alice。 - 步骤 3：Alice 生成了⼀棵具有 $4$ 个节点的树，其边集为 $\{\{1, 2\}, \{2, 3\}, \{2, 4\}\}$，将这棵树告诉 Catherine。 - 步骤 4：Catherine 删去了树中连接节点 $2$ 和 $3$ 的边，并把剩余的边 $\{\{1, 2\}, \{2, 4\}\}$ 告诉 Bob。 - 步骤 5：Bob 给出数字 $3$ 作为回答。由于他给出了正确答案，他们的魔术表演⼤获成功。 ### 子任务 1. (5 分)：$X\leq 5, 000$。 2. (30 分)：$X\leq25, 000, 000$。 3. (65 分)：没有特殊限制。