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 翻译