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

AT_abc160_f.[ABC160F] Distributing Integers

省选/NOI-

通过率：0%

AC君温馨提醒

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

题目描述

有一棵包含 NN 个顶点的树，顶点编号为 11 到 NN。这棵树的第 ii 条边连接了顶点 aia_i 和顶点 bib_i。

对于 k=1,…,Nk=1,\ldots,N，请解决以下问题：

  • 按照如下步骤，在树的每个顶点上写一个整数。
    • 首先，在顶点 kk 上写 11。
    • 然后依次将 2,…,N2,\ldots,N 写到顶点上。每次选择要写入的顶点时，需满足以下条件：
      • 该顶点尚未被写入整数，且与已写入整数的顶点相邻。如果有多个满足条件的顶点，则从中随机选择一个。
  • 求所有可能的整数写法的数量，并对 109+710^9+7 取模。

输入格式

输入以如下格式从标准输入读入。

NN
a1a_1 b1b_1
a2a_2 b2b_2
⋮\vdots
aN−1a_{N-1} bN−1b_{N-1}

输出格式

请按顺序输出 k=1,2,…,Nk=1,2,\ldots,N 的答案，每行一个。

输入输出样例

  • 输入#1

    3
1 2
1 3

    输出#1

    2
1
1

  • 输入#2

    2
1 2

    输出#2

    1
1

  • 输入#3

    5
1 2
2 3
3 4
3 5

    输出#3

    2
8
12
3
3

  • 输入#4

    8
1 2
2 3
3 4
3 5
3 6
6 7
6 8

    输出#4

    40
280
840
120
120
504
72
72

说明/提示

限制条件

  • 2≤N≤2×1052 \leq N \leq 2 \times 10^5
  • 1≤ai,bi≤N1 \leq a_i, b_i \leq N
  • 给定的图一定是一棵树

样例解释 1

该输入对应的图如下所示。

对于 k=1k=1 的情况，有如下两种整数写法：

  • 在顶点 1,2,31,2,3 上分别写 1,2,31,2,3
  • 在顶点 1,2,31,2,3 上分别写 1,3,21,3,2

样例解释 2

该输入对应的图如下所示。

样例解释 3

该输入对应的图如下所示。

样例解释 4

该输入对应的图如下所示。

由 ChatGPT 4.1 翻译

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

首页