[USACO23DEC] A Graph Problem P

Luogu

IDLGP9984

Time1000ms

Memory256MB

DifficultyP6

线段树USACO并查集2023Kruskal 重构树O2优化哈希 hashing启发式合并

为了丰富自己的数学知识，Bessie 选修了一门图论课程，她发现她被下面的问题困住了，请帮帮她！给出一张连通的无向图，包含编号为 $1\dots N$ 的节点和编号为 $1\dots M$（$2 \le N \le 2\cdot 10^5$，$N - 1 \le M \le 4 \cdot 10^5$）的边，下边的操作将被实施： 1. 假设集合 $S=\{v\}$，变量 $h=0$。 2. 当 $|S|<N$，重复执行： 1. 仅有一个顶点在集合 $S$ 中的边中，找到编号最小的那条，编号记为 $e$。 2. 将 $e$ 不在 $S$ 中的那个顶点加入集合 $S$。 3. 将 $h$ 修改为 $10h+e$。 3. 返回 $h$ 对 $10^9+7$ 取模的值。输出这个过程的全部返回值。 ## Input 第一行包含 $N$ 和 $M$。接下来 $M$ 行，每行包含第 $e$ 条边的顶点 $(a_e,b_e)$，保证图连通，没有重边。 ## Output 输出 $N$ 行，第 $i$ 行包含在节点 $i$ 开始过程的返回值。 [samples] ## Note ### 样例解释 2 考虑在 $i=3$ 开始执行。首先，选择 $2$ 号边，$S=\{3,4\}$，$h=2$。然后，选择 $3$ 号边，$S=\{2,3,4\}$，$h=23$。接着，选择 $1$ 号边，$S=\{1,2,3,4\}$，$h=231$。最后，选择 $5$ 号边，$S=\{1,2,3,4,5\}$，$h=2315$。因此，$i=3$ 的答案是 $2315$。 ### 样例解释 3 确保答案对 $10^9+7$ 取模。 ### 测试点性质 - 测试点 $4$ 满足 $N,M \le 2000$。 - 测试点 $5-6$ 满足 $N \le 2000$。 - 测试点 $7-10$ 满足 $N \le 10000$。 - 测试点 $11-14$ 满足对于所有边，有 $a_e+1=b_e$。 - 测试点 $15-23$ 没有额外限制。

Samples

Input #1

3 2
1 2
2 3

Output #1

12
12
21

Input #2

Output #2

Input #3

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[USACO23DEC] A Graph Problem P",
    "description": {
      "content": "为了丰富自己的数学知识，Bessie 选修了一门图论课程，她发现她被下面的问题困住了，请帮帮她！ 给出一张连通的无向图，包含编号为 $1\\dots N$ 的节点和编号为 $1\\dots M$（$2 \\le N \\le 2\\cdot 10^5$，$N - 1 \\le M \\le 4 \\cdot 10^5$）的边，下边的操作将被实施： 1. 假设集合 $S=\\{v\\}$，变量 $h=0$。 2. ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9984"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "为了丰富自己的数学知识，Bessie 选修了一门图论课程，她发现她被下面的问题困住了，请帮帮她！\n\n给出一张连通的无向图，包含编号为 $1\\dots N$ 的节点和编号为 $1\\dots M$（$2 \\le N \\le 2\\cdot 10^5$，$N - 1 \\le M \\le 4 \\cdot 10^5$）的边，下边的操作将被实施：\n\n1. 假设集合 $S=\\{v\\}$，变量 $h=0$。\n2. ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments