F - Tree Patrolling Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 頂点の木があり、各頂点には 1 から N までの番号が振られています。また、i 本目の辺は頂点 u_i と頂点 v_i を双方向に結んでいます。

この木の持ち主であるあなたは、いくつかの頂点 (0 個でもよい) を選んで高橋くんを配置し、木の警備をさせることにしました。頂点 x に配置された高橋くんは、x と直接辺で結ばれた頂点、及び x 自身を警備します。

高橋くんを配置する頂点の選び方は 2^N 通りありますが、そのうち 1 人以上の高橋くんに警備された頂点の個数がちょうど K 個となるような選び方はいくつありますか？

K=0,1,\ldots,N について答えを求め、(10^9+7) で割ったあまりを出力してください。

制約

  • 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

高橋くんを配置する頂点の選び方は、以下の 8 通りです。

  • どの頂点にも高橋くんを配置しない。いずれの頂点も高橋くんに警備されていない状態となる。
  • 頂点 1 に高橋くんを配置する。全ての頂点が高橋くんに警備された状態となる。
  • 頂点 2 に高橋くんを配置する。頂点 1, 2 の 2 つが高橋くんに警備された状態となる。
  • 頂点 3 に高橋くんを配置する。頂点 1, 3 の 2 つが高橋くんに警備された状態となる。
  • 頂点 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

Score : 600 points

Problem Statement

You have a tree with N vertices, numbered 1 through N. The i-th edge connects Vertex u_i and Vertex v_i.

You will choose some vertices (possibly none) and place a takahashi in each of them to guard the tree. A takahashi placed at Vertex x will guard x itself and the vertices directly connected to x by an edge.

There are 2^N ways to choose vertices for placing takahashi. In how many of them will there be exactly K vertices guarded by one or more takahashi?

Find this count and print it modulo (10^9+7) for each K=0,1,\ldots,N.

Constraints

  • 1 \leq N \leq 2000
  • 1 \leq u_i \lt v_i \leq N
  • The given graph is a tree.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print N+1 lines. The i-th line should contain the answer for K=i-1.

Sample Input 1

3
1 3
1 2

Sample Output 1

1
0
2
5

There are eight ways to choose vertices for placing takahashi, as follows:

  • Place a takahashi at no vertices, guarding no vertices.
  • Place a takahashi at Vertex 1, guarding all vertices.
  • Place a takahashi at Vertex 2, guarding Vertices 1 and 2.
  • Place a takahashi at Vertex 3, guarding Vertices 1 and 3.
  • Place a takahashi at Vertices 1 and 2, guarding all vertices.
  • Place a takahashi at Vertices 1 and 3, guarding all vertices.
  • Place a takahashi at Vertices 2 and 3, guarding all vertices.
  • Place a takahashi at all vertices, guarding all vertices.

Sample Input 2

5
1 3
4 5
1 5
2 3

Sample Output 2

1
0
2
5
7
17

Sample Input 3

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

Sample Output 3

1
0
3
8
15
32
68
110
196
266
325