Home » 国际竞赛 » Details

2023-2024年USACO首次月考题目出炉！白金级第二题真题及解析

Category: 国际竞赛, 翰林严选, 计算机国际竞赛 Date: 2024年1月2日上午11:25

2023-2024赛季的USACO考试已于12月18日正式结束，晋级赛的最新试题也已经公布。近日，USACO官方公布了2023-2024赛季首场月赛的晋级分数线。如果没有晋级，12月可以当做一个练手+熟悉赛制的环节，1、2月的月赛持续发力，USACO可以重复挑战。

今天给大家分享白金级试题和解析，参赛的同学来看看解题思路，没参赛的同学来看看难度如何？

USACO 2023年12月白金级第二题

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…N and edges labeled 1…M(2≤N≤2⋅10⁵, N−1≤M≤4⋅10⁵). For each vertex v in the graph, the following process is conducted：

Let S={v}and h=0.

While |S|<N,

1.Out of all edges with exactly one endpoint in S, let e be the edge with the minimum label.
2.Add the endpoint of e not in S to S.
3.Set h=10h+e.

Return h ( mod 10⁹+7).

Determine all the return values of this process.

INPUT FORMAT (pipe stdin)：

The first line contains N and M .Then follow M lines, the eth containing the endpoints (a_e,b_e) of the eth edge (1≤a_e<b_e≤N). It is guaranteed that these edges form a connected graph, and at most one edge connects each pair of vertices.

OUTPUT FORMAT (pipe stdout)：

Output N lines, where the ith line should contain the return value of the process starting at vertex i.

SAMPLE INPUT：

3 2
1 2
2 3

SAMPLE OUTPUT：

12
12
21

SAMPLE INPUT：

5 6
1 2
3 4
2 4
2 3
2 5
1 5

SAMPLE OUTPUT：

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.

SAMPLE INPUT：

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

SAMPLE OUTPUT：

678925929
678925929
678862929
678787329
678709839
678632097
178554320
218476543
321398766
431520989
542453212
653475435
764507558
875540761
986574081

Make sure to output the answers modulo 109+7.

SCORING：

Input 4： N,M≤2000
Inputs 5-6： N≤2000
Inputs 7-10： N≤10000
Inputs 11-14： a_e+1=b_e
for all e
Inputs 15-23： No additional constraints.

Problem credits： Benjamin Q_i

部分代码截图：