CF2206G Extra Transition

你正在开发一个包含 $n$ 个关卡的游戏，编号从 $1$ 到 $n$。这些关卡通过由 $m$ 条转换组成的网络相连，转换编号从 $1$ 到 $m$。第 $k$ 条转换连接了 $a_k$ 和 $b_k$ 这两个关卡，并且是双向的（$1 \le k \le m$）。 一次游戏流程从第 $1$ 关开始。每当玩家进入一个新的关卡，必须完成该关卡，然后移动到另一个通过转换直接连接且本轮尚未完成的关卡。当玩家完成第 $n$ 关时，本轮游戏流程成功结束。 从第 $1$ 关开始、以第 $n$ 关结束、且关卡两两不同的一个关卡序列，如果玩家能依照序列顺序在一次流程中完成关卡，则称其为一条“成功路径”。 如果转换网络满足以下两个条件，则称为“设计良好”： - 对于任意 $i$（$2 \le i \le n-1$），都存在一条包含关卡 $i$ 的成功路径。 - 对于任意一对关卡 $i$ 和 $j$（$2 \le i < j \le n-1$），以下两个条件至多同时满足一个： - 存在一条包含 $i$ 和 $j$ 的成功路径，且 $i$ 出现在 $j$ 之前。 - 存在一条包含 $i$ 和 $j$ 的成功路径，且 $j$ 出现在 $i$ 之前。 你的第一个任务是判断给定的转换网络是否为设计良好。 如果网络被判定为设计良好，你还有第二个任务。设 $S$ 为所有满足 $1 \le i < j \le n$ 的整数对 $(i, j)$ 的集合，满足 $i$ 和 $j$ 没有直接连接，并且如果在它们之间新增一条双向转换，网络依然保持设计良好。你需要计算如下和： $$ \sum_{(i, j) \in S} w_i w_j $$

第一行包含一个整数 $t$（$1 \le t \le 50\,000$），表示测试用例数。接下来有 $t$ 个测试用例。每个测试用例格式如下： 第一行包含两个整数 $n$ 和 $m$（$3 \le n \le 200\,000$；$n-1 \le m \le 200\,000$）。 第二行包含 $n$ 个整数 $w_1, w_2, \ldots, w_n$（$1 \le w_i \le 5000$，对于所有 $i$）。 接下来 $m$ 行，每行包含两个整数 $a_k$ 和 $b_k$（$1 \le a_k < b_k \le n$；对于所有 $k \ne \ell$，$(a_k, b_k) \ne (a_\ell, b_\ell)$）。 保证该转换网络是连通的：对于任意两关 $i$ 和 $j$（$i \ne j$），都存在一条由转换组成的路径，使得可以从 $i$ 到 $j$。 所有测试用例中 $n$ 之和不超过 $200\,000$。 所有测试用例中 $m$ 之和不超过 $200\,000$。

对于每个测试用例，如果该转换网络不是设计良好，输出 bad。否则，输出上述定义的和。

对于第一个测试用例，给出的转换网络是设计良好的。可以加入额外转换的候选 $(i, j)$ 有 $(1, 4)$ 和 $(2, 3)$。 - 对于 $(1, 4)$，在它们之间新增一条转换后，网络依然设计良好。 - 对于 $(2, 3)$，新增它们之间的转换后不能保持设计良好。存在两条成功路径 $(1, 2, 3, 4)$ 和 $(1, 3, 2, 4)$，对于关卡 $2$ 和 $3$，第二个条件不再满足。 因此答案为 $w_1 w_4 = 1 \times 4 = 4$。对于第二个测试用例，给定的转换网络不是设计良好，因为没有包含关卡 $2$ 的成功路径。 由 ChatGPT 5 翻译