← 返回题目列表

AtCoder · abc207_f

F. 树巡逻

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

你有一棵树 N 顶点,编号 1 通过 N。的 i第一条边连接顶点 u_i 和顶点 v_i.

您将选择一些顶点(可能没有)并在每个顶点中放置一个高桥来保护树。放置在 Vertex 的高桥 x 将守护 x 本身和直接连接到的顶点 x 的边缘。

有 2^N 选择放置高桥顶点的方法。其中到底有多少个 K 顶点由一个或多个高桥守护?

找到这个计数并打印它的模数 (10^9+7) 对于每个 K=0,1,\ldots,N.

约束

  • 1 \leq N \leq 2000
  • 1 \leq u_i \lt v_i \leq N
  • 给定的图是一棵树。
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
u_1 v_1
u_2 v_2
\hspace{0.6cm}\vdots
u_{N-1} v_{N-1}

输出

打印 N+1 行。的 i- 第行应包含以下问题的答案 K=i-1.


示例输入 1

3
1 3
1 2

示例输出 1

1
0
2
5

有八种方式选择放置高桥的顶点,如下:

  • 在没有顶点处放置高桥,不保护任何顶点。
  • 在顶点放置高桥 1,保护所有顶点。
  • 在顶点放置高桥 2,保护顶点 1 和 2.
  • 在顶点放置高桥 3,保护顶点 1 和 3.
  • 在顶点处放置高桥 1 和 2,保护所有顶点。
  • 在顶点处放置高桥 1 和 3,保护所有顶点。
  • 在顶点处放置高桥 2 和 3,保护所有顶点。
  • 在所有顶点放置高桥,守卫所有顶点。

示例输入 2

5
1 3
4 5
1 5
2 3

示例输出 2

1
0
2
5
7
17

示例输入 3

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

示例输出 3

1
0
3
8
15
32
68
110
196
266
325