2023-2024年USACO首次月考題目出爐！白金級第二題真題及解析
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?105, N?1≤M≤4?105). 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 109+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 (ae,be) of the eth edge (1≤ae<be≤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： ae+1=be
for all e
Inputs 15-23： No additional constraints.
Problem credits： Benjamin Qi
部分代碼截圖：
USACO歷年真題及參考書，掃碼領?。 竞擦痔峁﹫竺笇Х铡?/strong>
USACO歷年真題及參考書
2023-2024年USACO活動時間
第一次月賽：2023年12月15日-18日
第二次月賽：2024年1月26日-29日
第三次月賽：2024年2月16日-19日
美國公開賽：2024年3月15日-18日
（中國學生只能參加到公開賽）
集訓營：2024年5月23日-6月1日
EGOI：2024年7月21日-27日（荷蘭）
IOI：2024年9月1日-8日（埃及）
報名方式：參賽者可隨時在官網注冊賬號，注冊。報名，只需在活動時間登陸完成答題即可。
官網地址：usaco.org
提交之后，官網會發送一份郵件到您郵箱，郵件中有賬號密碼
利用已知的賬號于密碼，登錄USACO賬號，即可開始考試
翰林AMC8視頻課重磅上線！
國際競賽真題資源免費領取
