#PU1092. USACO 2021 January Contest, Platinum — Problem 1. Sum of Distances
USACO 2021 January Contest, Platinum — Problem 1. Sum of Distances
USACO 2021 January Contest, Platinum — Problem 1. Sum of Distances
题目描述
Bessie has a collection of connected, undirected graphs (). For each , has exactly () vertices labeled and () edges. Each may contain self-loops, but not multiple edges between the same pair of vertices. Now Elsie creates a new undirected graph with vertices, each labeled by a -tuple where . In , two vertices and are connected by an edge if for all , and are connected by an edge in . Define the distance between two vertices in that lie in the same connected component to be the minimum number of edges along a path from one vertex to the other. Compute the sum of the distances between vertex and every vertex in the same component as it in , modulo .
输入格式
The first line contains , the number of graphs. Each graph description starts with and on a single line, followed by edges. Consecutive graphs are separated by newlines for readability. It is guaranteed that and .
输出格式
The sum of the distances between vertex and every vertex that is reachable from it, modulo .
数据范围
Test cases 3-4 satisfy . Test cases 5-10 satisfy . Test cases 11-20 satisfy no additional constraints. Problem credits: Benjamin Qi
样例
样例 1
2
2 1
1 2
4 4
1 2
2 3
3 4
4 1
4
$G$ contains $2\cdot 4=8$ vertices, $4$ of which are not connected to vertex
$(1,1)$. There are $2$ vertices that are distance $1$ away from $(1,1)$ and $1$
that is distance $2$ away. So the answer is $2\cdot 1+1\cdot 2=4$.
样例 2
3
4 4
1 2
2 3
3 1
3 4
6 5
1 2
2 3
3 4
4 5
5 6
7 7
1 2
2 3
3 4
4 5
5 6
6 7
7 1
706
$G$ contains $4\cdot 6\cdot 7=168$ vertices, all of which are connected to
vertex $(1,1,1)$. The number of vertices that are distance $i$ away from
$(1,1,1)$ for each $i\in [1,7]$ is given by the $i$-th element of the following
array:
$[4,23,28,36,40,24,12]$.