F - 树的巡逻

得分：$600$ 分

题目描述

给定一棵 $N$ 个节点的树，节点编号从 $1$ 到 $N$。第 $i$ 条边连接了节点 $u_i$ 和节点 $v_i$。

你可以选择一些节点（可能为零），并在每个选中的节点上放置一个“守护者”来守卫这棵树。放置在节点 $x$ 上的守卫将守卫节点 $x$ 本身以及与 $x$ 相邻的节点（通过一条边直接相连）。

有 $2^N$ 种选择方式可以放置守卫。现在，你需要计算在这些选择中，有多少种选择方式会使得恰好 $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$ 的答案。

3
1 3
1 2

1
0
2
5

有 $8$ 种选择方式可以放置守卫，具体如下：

• 不在任何节点放置守卫，没有节点被守卫。
• 在节点 $1$ 上放置守卫，守卫所有节点。
• 在节点 $2$ 上放置守卫，守卫节点 $1$ 和节点 $2$。
• 在节点 $3$ 上放置守卫，守卫节点 $1$ 和节点 $3$。
• 在节点 $1$ 和节点 $2$ 上都放置守卫，守卫所有节点。
• 在节点 $1$ 和节点 $3$ 上都放置守卫，守卫所有节点。
• 在节点 $2$ 和节点 $3$ 上都放置守卫，守卫所有节点。
• 在所有节点上都放置守卫，守卫所有节点。

5
1 3
4 5
1 5
2 3

1
0
2
5
7
17

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

1
0
3
8
15
32
68
110
196
266
325