题目详情题解（0）讨论（0）提交记录（0）

AT_abc419_g.[ABC419G] Count Simple Paths 2

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个包含 NN 个顶点（编号为 11 到 NN）和 MM 条边的简单连通无向图。第 ii 条边连接顶点 uiu_i 和 viv_i。

对于每个 k=1,2,…,N−1k=1,2,\ldots,N-1，请你求出从顶点 11 到顶点 NN 恰好经过 kk 条边的简单路径的数量。

输入格式

输入从标准输入读入，格式如下：

NN MM
u1u_1 v1v_1
u2u_2 v2v_2
⋮\vdots
uMu_M vMv_M

输出格式

请按如下格式输出答案：

ans1\mathrm{ans}_1 ans2\mathrm{ans}_2 …\ldots ansN−1\mathrm{ans}_{N-1}

其中，ansi\mathrm{ans}_i 表示从顶点 11 到顶点 NN 恰好经过 ii 条边的简单路径的数量。

输入输出样例

  • 输入#1

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

    输出#1

    0 1 2 1

  • 输入#2

    11 15
1 2
1 3
2 3
3 4
3 5
4 5
5 6
5 7
6 7
7 8
7 9
8 9
9 10
9 11
10 11

    输出#2

    0 0 0 0 1 5 10 10 5 1

  • 输入#3

    7 18
6 7
4 5
1 7
2 7
1 4
2 5
4 6
2 3
5 6
5 7
1 5
2 4
2 6
1 2
1 3
3 4
1 6
3 5

    输出#3

    1 3 11 29 50 42

说明/提示

样例解释 1

对于每个 k=1,2,3,4k=1,2,3,4，从顶点 11 到顶点 55 恰好经过 kk 条边的简单路径如下：

  • k=1k=1：无
  • k=2k=2：1→3→51\to 3\to 5
  • k=3k=3：1→2→4→51\to 2\to 4\to 5 和 1→3→4→51\to 3\to 4\to 5
  • k=4k=4：1→2→4→3→51\to 2\to 4\to 3\to 5

数据范围

  • 2≤N≤2×1052\leq N\leq 2\times 10^5
  • N−1≤M≤N+20N-1\leq M\leq N+20
  • 1≤ui<vi≤N1\leq u_i < v_i \leq N
  • 给定的图是一个简单连通无向图。
  • 所有输入值均为整数。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页