P7499 - A Very Easy Graph Problem

内存限制：128 MB 时间限制：1 S

题面：传统评测方式：文本比较上传者：

提交：23 通过：18

提交提交记录统计 Web Board

An undirected connected graph has

n nodes and

m edges, The

i-th edge’s length is

2i. Each node

i has a value

ai, which is either

0 or

1. You need to calculate:

\sumi=1n\sumj=1nd(i,j)\times[ai=1\landaj=0]

d(i,j) indicates the shortest distance between

i and

[ ] is the Iverson bracket.

∧ indicates

AND.

Because the answer may be too large, please output the answer modulo

109+7.

The first line contains one integer

1≤T≤8)，indicating the number of test cases.
The second line contains two ingeters

n,m(

1≤n≤105,1≤m≤2×105).
The third line contains

npositive integers

a1,a2,...,an(ai=0or

1) —— the value of the nodes.
The following

mlines contain two ingeters

u,v(1≤u,v≤n), and the

i-th line represents the i-th undirected edge’s length is

2i, between node

uand

v.
The sum of

n,mis no more than

2×105.

Print a single integer—— the value of the answer modulo

109+7

2020 Multi-University Training Contest 6

7499: A Very Easy Graph Problem

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

分类标签