A6151. 「USACO 2023.12 Platinum」A Graph Problem
编程题
省选/NOI-
知识点
题目描述
**题目译自 [USACO 2023 December Contest, Platinum](http://usaco.org/index.php?page=dec23results) Problem 2. [A Graph Problem](http://usaco.org/index.php?page=viewproblem2&cpid=1357)**
为了提高自己的数学知识，Bessie 一直在学习图论课程，她发现自己被下面的问题难住了。请帮帮她！
给定一个无向连通图，点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。对于图中的每个点 $v$ 进行如下操作：
1. 令 $S=\{v\}$ 且 $h=0$。
2. 当 $|S|<N$ 时
1. 对于满足只有一个端点在 $S$ 中的所有边，令 $e$ 为满足条件的边中编号最小的一条。
2. 将不在 $S$ 中的端点加入 $S$。
3. 令 $h=10h+e$。
3. 返回 $h\pmod {10^9+7}$
确定这个过程的所有返回值。
为了提高自己的数学知识，Bessie 一直在学习图论课程，她发现自己被下面的问题难住了。请帮帮她！
给定一个无向连通图，点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。对于图中的每个点 $v$ 进行如下操作：
1. 令 $S=\{v\}$ 且 $h=0$。
2. 当 $|S|<N$ 时
1. 对于满足只有一个端点在 $S$ 中的所有边，令 $e$ 为满足条件的边中编号最小的一条。
2. 将不在 $S$ 中的端点加入 $S$。
3. 令 $h=10h+e$。
3. 返回 $h\pmod {10^9+7}$
确定这个过程的所有返回值。
输入格式
第一行包含两个整数 $N\ (2\le N\le 2\cdot 10^5)$ 和 $M\ (N-1\le M\le 4\cdot 10^5)$。
接下来 $M$ 行，第 $e$ 行包含第 $e$ 条边的两个端点 $(a_e,b_e)\ (1\le a_e<b_e\le N)$。保证这些边构成一张连通图，并且每对顶点最多由一条边相连。
接下来 $M$ 行，第 $e$ 行包含第 $e$ 条边的两个端点 $(a_e,b_e)\ (1\le a_e<b_e\le N)$。保证这些边构成一张连通图，并且每对顶点最多由一条边相连。
输出格式
输出 $N$ 行，第 $i$ 行表示操作从点 $i$ 开始的情况下最终的返回值。
输入输出样例
输入 #1
3 2 1 2 2 3
输出 #1
12 12 21
输入 #2
5 6 1 2 3 4 2 4 2 3 2 5 1 5
输出 #2
1325 1325 2315 2315 5132
输入 #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
输出 #3
678925929 678925929 678862929 678787329 678709839 678632097 178554320 218476543 321398766 431520989 542453212 653475435 764507558 875540761 986574081
说明/提示
- 测试点 $4$：$N,M\le 2000$
- 测试点 $5\sim 6$：$N\le 2000$
- 测试点 $7\sim 10$：$N\le 10^4$
- 测试点 $11\sim 14$：对于所有 $e$ 满足 $a_e+1=b_e$
- 测试点 $15\sim 23$：无附加限制
Problem credits: Benjamin Qi
- 测试点 $5\sim 6$：$N\le 2000$
- 测试点 $7\sim 10$：$N\le 10^4$
- 测试点 $11\sim 14$：对于所有 $e$ 满足 $a_e+1=b_e$
- 测试点 $15\sim 23$：无附加限制
Problem credits: Benjamin Qi