一个非常简单的图论问题

题目描述

给定一个有 $n$ 个点、$m$ 条边的无向连通图。

按照输入顺序编号，第 $i$ 条边的长度为 $2^i$。

每个点 $i$ 有一个值 $a_i$，其中 $a_i$ 只能是 $0$ 或 $1$。

你需要计算

$\displaystyle \sum_{i=1}^{n}\sum_{j=1}^{n} d(i,j)\times [a_i=1\land a_j=0]$

其中：

• $d(i,j)$ 表示点 $i$ 到点 $j$ 的最短路长度；
• $[\ ]$ 是 Iverson 括号，当括号中的条件成立时值为 $1$，否则为 $0$；
• $\land$ 表示逻辑与。

换句话说，对于所有满足 $a_i=1$ 且 $a_j=0$ 的有序点对 $(i,j)$，求它们之间的最短路长度之和。

由于答案可能非常大，请输出答案对 $10^9+7$ 取模后的结果。

输入格式

第一行包含一个整数 $T$，表示测试数据组数。

$1\le T\le 8$

对于每组测试数据：

第一行包含两个整数 $n,m$，表示点数和边数。

$1\le n\le 10^5,\quad 1\le m\le 2\times 10^5$

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，其中 $a_i\in{0,1}$。

接下来 $m$ 行，每行包含两个整数 $u,v$，表示一条连接点 $u$ 和点 $v$ 的无向边。

其中，第 $i$ 行给出的边是第 $i$ 条边，它的长度为 $2^i$。

$1\le u,v\le n$

保证所有测试数据中 $n,m$ 的总规模不超过 $2\times 10^5$。

输出格式

对于每组测试数据，输出一行一个整数，表示答案对 $10^9+7$ 取模后的结果。

样例

1
3 2
0 1 0
3 1
3 2

10

样例解释

两条边的长度分别为：

• $3\leftrightarrow 1$，长度为 $2^1=2$；
• $3\leftrightarrow 2$，长度为 $2^2=4$。

只有点 $2$ 的值为 $1$。

因此需要计算：

• $d(2,3)=4$；
• $d(2,1)=4+2=6$。

答案为 $4+6=10$。

来源

2020 Multi-University Training Contest 6