← 返回题目列表

Codeforces · 2206/G

G. 额外过渡

中文机器翻译题面 查看原题

您正在开发一款由 $$$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 \lt j \le n-1$$$),最多满足以下条件之一:
    • 存在一条包含级别 $$$i$$$ 和 $$$j$$$ 的成功路径,其中级别 $$$i$$$ 出现在级别 $$$j$$$ 之前。
    • 存在一条包含级别 $$$i$$$ 和 $$$j$$$ 的成功路径,其中级别 $$$j$$$ 出现在级别 $$$i$$$ 之前。

你的 第一 任务是确定给定的转换网络是否设计良好。

如果网络设计良好,你就有了 第二 任务。令 $$$S$$$ 为整数对 $$$(i, j)$$$ ($$$1 \le i \lt j \le n$$$) 的集合,这样级别 $$$i$$$ 和 $$$j$$$ 不会直接连接,并且在它们之间添加双向额外转换可以保持网络设计良好。您对 $$$S$$$ 套装感兴趣。给定一个由 $$$n$$$ 整数 $$$w_1, \ldots, w_n$$$ 组成的序列。作为 $$$S$$$ 的汇总,计算以下总和:$$\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$$$ 行中的第 $$$k$$$ 行包含两个整数 $$$a_k$$$ 和 $$$b_k$$$ ($$$1 \le a_k \lt b_k \le n$$$; $$$(a_k, b_k) \not= (a_\ell, b_\ell)$$$ 对于所有 $$$k \not= \ell$$$)。

输入保证转换网络是 已连接;对于任何级别 $$$i$$$ 和 $$$j$$$ ($$$i \not= j$$$),都存在从级别 $$$i$$$ 到级别 $$$j$$$ 的转换序列。

一个输入文件中所有测试用例的 $$$n$$$ 总和不超过 $$$200\,000$$$。

一个输入文件中所有测试用例的 $$$m$$$ 总和不超过 $$$200\,000$$$。

输出

对于每个测试用例,如果过渡网络设计不完善,则输出 坏。否则,输出上面定义的总和。

示例

输入
复制

3
4 4
1 2 3 4
1 2
1 3
2 4
3 4
3 2
2026 3 9
1 3
2 3
10 11
15 51 82 49 1 55 45 5 25 91
7 10
1 6
2 5
4 7
3 8
1 9
4 6
2 10
3 9
5 9
2 8

输出
复制

4
bad
23336

注意

对于第一个测试用例,给定的转换网络经过精心设计。添加额外转换 $$$(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$$$ 的成功路径。