AT_oupc2023_day1_p Score for Cutting Graph

对于一个无向图 $G'$，每个顶点上写有一个正整数，定义 $G'$ 的分数如下： - 对于 $G'$ 的每个连通分量，计算该连通分量中所有顶点上正整数的乘积，并将这些乘积累加起来，得到总分数。 给定一个只包含正整数的长度为 $N$ 的序列 $A = (A_1, A_2, \ldots, A_N)$ 和一个正整数 $M$。现在需要构造一个编号分别为 $1$ 到 $N$ 的 $N$ 个顶点、$N-1$ 条边的简单且连通的无向图 $G$，使得满足下列条件： - 对于 $G$ 的每个顶点 $i$（$1 \leq i \leq N$），点 $i$ 上写有 $A_i$。 - 从 $G$ 删除至多一条边后得到的所有 $N$ 个图，它们的分数总和不超过 $M$。 有 $T$ 个测试用例，请分别判断每个测试用例是否存在符合条件的 $G$。如果存在，请给出构造方案。

输入按如下格式从标准输入读入： > $T$ $\mathrm{case}_1$ $\vdots$ $\mathrm{case}_T$ 每个测试用例格式如下： > $N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$

对于第 $k$ 个测试用例，输出该用例的答案。如果无法使分数总和不超过 $M$，输出 `No`。否则，第一行输出 `Yes`，后面 $N-1$ 行输出 $G$ 的边的构造方式，格式如下： > $s_1$ $t_1$ > $s_2$ $t_2$ > $\vdots$ > $s_{N-1}$ $t_{N-1}$ 其中 $s_j, t_j$ 表示 $G$ 的第 $j$ 条边（连接顶点 $s_j$ 与 $t_j$）。 如果存在多种方案，输出任意一种均可。

## 子任务 1. （1 分）$N \leq 7$ 2. （99 分）无额外约束 ### 样例解释 1 第 1 个测试用例及其输出结果如下所示，例如： - 不删除任何边时，分数为 $(1 \times 2 \times 3 \times 4) = 24$。 - 删除第 1 条边时，分数为 $(2) + (1 \times 3 \times 4) = 14$。 - 删除第 2 条边时，分数为 $(3) + (1 \times 2 \times 4) = 11$。 - 删除第 3 条边时，分数为 $(4) + (1 \times 2 \times 3) = 10$。 分数总和为 $59$。也存在分数总和不超过 $60$ 的其它 $G$，输出任意一种即可。 对于第 2 个测试用例，无法使分数总和不超过 $24$，因此输出 `No`。 此样例满足子任务 1 的约束。 ### 样例解释 2 此样例不满足子任务 1 的约束。 ### 数据范围 - $1 \leq T \leq 5$ - $2 \leq N \leq 200,\!000$ - $1 \leq M \leq 10^{18}$ - $1 \leq A_i \leq 10^{18}$ - 所有测试用例中 $N$ 的总和不超过 $200,\!000$ - 输入均为整数。 由 ChatGPT 5 翻译