AT_future_contest_2020_final_2_a 千の木2

在二维坐标平面上，分布着 $N$ 个顶点，编号为 $1$ 到 $N$。此外，还给出了 $S$ 个无向树 $T_1, \ldots, T_S$。 你的任务是将这些顶点连接起来，构造一个包含 $N$ 个顶点的无向图 $G$，并从中“提取”出 $S$ 个子图。被提取出的子图越“接近” $T_1, \ldots, T_S$ 所描述的结构，得分越高。下面对题目条件进行详细解释： - 顶点信息：每个顶点 $i$ 的坐标是 $(x_i, y_i)$，其中 $x_i, y_i$ 是 $0$ 到 $1000$ 之间的整数。每个顶点都有一个正整数“功率”，记为 $c_i$。 - 关于树：每棵无向树 $T_i$ 由 $K_i$ 个顶点构成，其中每个顶点标号为 $1$ 到 $K_i$。输入给出的树是根为 $1$ 的有根树，树 $T_i$ $(1 \leq i \leq S)$ 中每个编号为 $j$ 的顶点（$2 \leq j \leq K_i$）的父节点编号为 $p_{i,j}$。 - 边的添加：构建的图 $G$ 可以包含 $0$ 到 $100000$ 条不等的无向边。若要连接顶点 $i$ 和 $j$，要求它们之间的欧几里得距离不超过 $c_i + c_j$。注意，图中不允许有自环和重边。 - 子图的提取：对于每棵树 $T_i$ $(1 \leq i \leq S)$，选择 $G$ 中的 $K_i$ 个不同顶点 $V_{i,1}, \ldots, V_{i,K_i}$，使得 $V_{i,j}$ 对应 $T_i$ 中编号为 $j$ 的顶点。同一顶点可以用于不同的树。 - 得分计算：对每棵树 $T_i$ $(1 \leq i \leq S)$，按以下规则得分，所有树的得分总和即为该测试用例的得分： - 如果存在 $x, y$ $(1 \leq x, y \leq K_i)$，使得 $T_i$ 包含边 $\{x, y\}$ 但 $G$ 不含 $\{V_{i,x}, V_{i,y}\}$，则得分为 $0$。 - 否则，设 $G$ 中多余的边对 $(x, y)$ 的数目为 $e_i$，这些边在 $T_i$ 中不存在。得分如下： - 若 $e_i = 0$，则得分 $100$。 - 若 $e_i = 1$，则得分 $10$。 - 若 $e_i = 2$，则得分 $1$。 - 若 $e_i \geq 3$，则得分 $0$。

输入采用以下格式： > $N$ $S$ $x_1$ $y_1$ $c_1$ $x_2$ $y_2$ $c_2$ $\cdots\ x_N$ $y_N$ $c_N$ $K_1$ $p_{1,2}$ $p_{1,3}$ $\ldots$ $p_{1,K_1}$ $K_2$ $p_{2,2}$ $p_{2,3}$ $\ldots$ $p_{2,K_2}$ $\cdots\ K_S$ $p_{S,2}$ $p_{S,3}$ $\ldots$ $p_{S,K_S}$

输出采用以下格式： > $M$ $A_1$ $B_1$ $A_2$ $B_2$ $\cdots\ A_M$ $B_M$ $V_{1,1}$ $V_{1,2}$ $\cdots\ V_{1,K_1}$ $V_{2,1}$ $V_{2,2}$ $\cdots\ V_{2,K_2}$ $\cdots\ V_{S,1}$ $V_{S,2}$ $\cdots\ V_{S,K_S}$ 这说明构建的图 $G$ 有 $M$ $(0 \leq M \leq 100000)$ 条边 $\{A_1, B_1\}, \{A_2, B_2\}, \ldots, \{A_M, B_M\}$，其中 $1 \leq A_i, B_i \leq N$。边的顺序以及边两端点的顺序可以任意。关于 $V_{i,j}$，请参见题目描述。

### 数据约束 - $N = 1000$ - $S = 1000$ - $2 \leq K_i \leq 100$ - $0 \leq x_i, y_i \leq 1000$ - $1 \leq c_i \leq 1500$ - Tree 父节点编号 $p_{i,j}$ 满足 $1 \leq p_{i,j} \leq j-1$ - 所有输入值均为整数 ### 测试用例生成方法 - 坐标 $(x_i, y_i)$ 以独立均匀分布的方式从 $0$ 到 $1000$ 的整数中随机选择。 - 每个顶点以各自的概率成为强、中、弱顶点，从而决定功率 $c_i$ 的取值范围： - 强顶点：$c_i$ 在 $200$ 到 $500$ 之间均匀随机。 - 中顶点：$c_i$ 在 $50$ 到 $200$ 之间均匀随机。 - 弱顶点：$c_i$ 在 $1$ 到 $50$ 之间均匀随机。 - 每棵树的结构是通过随机选定父节点 $p_{i,j}$ 构建的，父节点从 $1$ 到 $j-1$ 中随机选择。 ### 示例输入输出 示例输入和输出可以从 [这个链接](https://img.atcoder.jp/future-contest-2020-final-2/5d0f79985f1f06c9f75730a2d9e72045.zip) 下载。 **本翻译由 AI 自动生成**