#PU1357. USACO 2023 December Contest, Platinum — Problem 2. A Graph Problem

    ID: 1293 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:dec23来源:usaco.orgscoring:equal_test_cases广搜模拟

USACO 2023 December Contest, Platinum — Problem 2. A Graph Problem

USACO 2023 December Contest, Platinum — Problem 2. A Graph Problem

题目描述

To improve her mathematical knowledge, Bessie has been taking a graph theory course and finds herself stumped by the following problem. Please help her! You are given a connected, undirected graph with vertices labeled 1…N1\dots N and edges labeled 1…M1\dots M (2≤N≤2⋅1052\le N\le 2\cdot 10^5, N−1≤M≤4⋅105N-1\le M\le 4\cdot 10^5). For each vertex vv in the graph, the following process is conducted: ​ Let S={v}S=\{v\} and h=0h=0. While ∣S∣<N|S|<N, ​ Out of all edges with exactly one endpoint in SS, let ee be the edge with the minimum label. Add the endpoint of ee not in SS to SS. Set h=10h+eh=10h+e. ​ Return h(mod109+7)h\pmod{10^9+7}. ​ Determine all the return values of this process. ​

输入格式

The first line contains NN and MM. ​ Then follow MM lines, the eeth containing the endpoints (ae,be)(a_e,b_e) of the eeth edge (1≤ae<be≤N1\le a_e<b_e\le N). It is guaranteed that these edges form a connected graph, and at most one edge connects each pair of vertices. ​

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

3 2
1 2
2 3
12
12
21

样例 2

5 6
1 2
3 4
2 4
2 3
2 5
1 5
1325
1325
2315
2315
5132
Consider starting at $i=3$. First, we choose edge $2$, after which
$S = \{3, 4\}$ and $h = 2$. Second, we choose edge $3$, after which
$S = \{2, 3, 4\}$ and $h = 23$. Third, we choose edge $1$, after which
$S = \{1, 2, 3, 4\}$ and $h = 231$. Finally, we choose edge $5$, after which
$S = \{1, 2, 3, 4, 5\}$ and $h = 2315$. The answer for $i=3$ is therefore
$2315$.

样例 3

15 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
678925929
678925929
678862929
678787329
678709839
678632097
178554320
218476543
321398766
431520989
542453212
653475435
764507558
875540761
986574081
Make sure to output the answers modulo $10^9+7$.