Score : $600$ points

问题描述

你拥有一棵包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。

你需要选择一些顶点（可能一个都不选）并在其中放置高桥守卫来保护这棵树。放置在顶点 $x$ 的高桥守卫将守护顶点 $x$ 本身以及通过边直接与 $x$ 相连的所有顶点。

共有 $2^N$ 种选择顶点放置高桥守卫的方式。其中有多少种方式能够使得恰好有 $K$ 个顶点被一个或多个高桥守卫守护？

请计算这个计数，并对每种情况下的 $K=0,1,\ldots,N$，将结果模 $(10^9+7)$ 后输出。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 09:21:17