P11252 [KTSC 2024 R2] 岛屿

**请使用 C++17 或 C++20 提交本题** 你需要在程序开头加入如下代码： ```cpp #include #include void construct_two_trees(int N, std::vector U, std::vector V); int add_vertex(int a, int b, int c); void report(std::vector tree); ```

**题目译自 [2024년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사](https://www.ioikorea.kr/archives/ioitst/2024/) T1 「[섬](https://assets.ioikorea.kr/ioitst/2024/2/island/island_statement.pdf)」** IOI 国建立在一个正 $N$ 边形的岛屿上。每个顶点代表一个区域，这些区域按顺时针方向依次编号为 $0, 1, \cdots, N-1$。IOI 国的道路网络由以下两种道路组成： - **海滨道路**：海滨道路连接正 $N$ 边形相邻顶点对应的区域，共有 $N$ 条道路。也就是说，对于所有 $i$ $(0 \leq i \leq N-2)$，存在连接 $i$ 区域和 $i+1$ 区域的道路，并且存在连接 $N-1$ 区域和 0 区域的道路。 - **内陆道路**：内陆道路连接不直接相邻的两个区域，共有 $N-3$ 条道路。这些道路除了端点外不相交，即它们对应于正 $N$ 边形中不相交的 $N-3$ 条对角线。 对于连接 $K$ 个区域的道路网络，如果道路集合 $T$ 满足以下条件，则称 $T$ 为一棵树： - $|T|=K-1$ - 仅使用 $T$ 中的道路可以在所有区域之间通行。 树在连接所有区域的运输中起着重要作用。如果在一棵树的道路无法使用时，仍有另一棵树可以使用，这将大大提高稳定性。因此，如果道路网络中存在两棵树 $T_1$ 和 $T_2$，且 $T_1 \cap T_2 = \emptyset$，即没有任何道路重叠，则称该道路网络为良好道路网络。 IOI 国计划通过以下方式建设新的区域和道路，以构建良好道路网络： - **区域建设**：对于区域 $a, b, c$，如果存在连接 $a$ 和 $b$、$b$ 和 $c$、$c$ 和 $a$ 的道路，则在这三个区域形成的三角形的内心处建立一个新区域 $d$，并连接 $a$ 和 $d$、$b$ 和 $d$、$c$ 和 $d$。新区域 $d$ 的编号从 $N$ 开始依次递增。对于相同的三个区域，不能进行多次区域建设，即每次建设使用的区域集合 $\{a, b, c\}$ 必须不同。 IOI 国可以进行多次区域建设，但希望通过尽可能少的建设次数，构建出没有重叠道路的两棵树的良好道路网络。请注意，良好道路网络不仅包括原有的 $N$ 个区域，还包括新建的区域。你需要帮助 IOI 国解决这个道路网络问题。即使没有最小化建设次数，也可以获得部分分数。 你需要实现以下函数： ```cpp void construct_two_trees(int N, std::vector U, std::vector V); ``` - `U, V`：大小为 $N-3$ 的整数数组。对于所有 $i$ $(0 \leq i \leq N-4)$，存在连接 $U[i]$ 和 $V[i]$ 的内陆道路。 - 该函数只会被调用一次，你需要在该函数内调用后续定义的 `add_vertex` 函数进行区域建设，并找到不共享道路的两棵树，然后调用 `report` 函数报告结果。 ```cpp int add_vertex(int a, int b, int c); ``` - 该函数表示在区域 $a, b, c$ 之间进行区域建设。 - 在调用该函数之前，区域 $a, b, c$ 中任意两个区域必须直接相连。 - 对于相同的三个区域，不能多次调用该函数，即每次建设使用的区域集合 $\{a, b, c\}$ 必须不同。 - 该函数返回新建区域的编号。即，当该函数第 $j$ 次执行时，返回 $N-1+j$。 - 在调用 `report` 函数后，不应再调用该函数。 ```cpp void report(std::vector tree); ``` - 该函数用于报告找到的树。 - 在 `construct_two_trees` 函数中，所有 `add_vertex` 函数调用结束后，必须准确调用两次该函数。 - 参数 `tree` 的每个元素是一个包含两区域编号的数组 `std::array`。区域编号的顺序无关紧要。 - 两次调用 `report(T1), report(T2)` 时，$T_1$ 和 $T_2$ 不应共享道路，并且每棵树的道路应能连接所有区域，包括新建区域。

示例评测程序按以下格式读取输入： - 第 $1$ 行：$N$ - 第 $2+i$ $(0 \leq i \leq N-4)$ 行：$U[i]\,V[i]$

示例评测程序按以下格式输出： 每次调用 `report` 函数时，评测程序输出： - 第 $1$ 行：整数 $k$，表示第 $k$ 次调用 `report` 函数。 - 第 $2$ 行：树的道路数量 $M$ - 第 $2+i$ $(1 \leq i \leq M)$ 行：树的第 $i$ 条道路的两个端点编号 $A[i]\,B[i]$ 在 `construct_two_trees` 函数执行完毕后，评测程序输出 `add_vertex` 函数的调用信息： - 第 $1$ 行：`add_vertex` 函数的总调用次数 $K$ - 第 $1+i$ $(1 \leq i \leq K)$ 行：`add_vertex` 函数第 $i$ 次调用的参数 $A[i]\,B[i]\,C[i]$

对于所有输入数据，满足： - $3 \leq N \leq 2\cdot 10^5$ - 对于所有 $i$ $(0 \leq i \leq N-4)$： - $0 \leq U[i], V[i] \leq N-1$ - $U[i] \neq V[i]$ - 给定的 $U$ 和 $V$ 满足内陆道路的条件。 详细子任务附加限制及分值如下表所示。 | 子任务 | 分值 | 附加限制 | | :-: | :-: | :-: | | $1$ | $6$ | $N \leq 5$ | | $2$ | $8$ | 存在一个区域与除自己外的所有区域直接相连 | | $3$ | $14$ | 初始状态下，对于所有可能的区域对 $(a, b, c)$，连接这三个区域的三条道路中至少有一条是海滨道路 | | $4$ | $21$ | $N \leq 5000$ | | $5$ | $51$ | 无附加限制 | 当 `construct_two_trees` 函数正确解决了问题时，如果 `add_vertex` 的调用次数大于最小值但不超过 $N$，则可以获得 $40\%$ 的分数。如果 `add_vertex` 的调用次数超过 $N$，则无法获得分数。可以证明，在给定限制条件下，可以通过不超过 $N$ 次调用 `add_vertex` 构建良好道路网络。