Tree Patrolling

题目描述

你有一棵包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$。第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。 你将选择若干顶点（可以不选）并在每个选中的顶点上放置一个 takahashi 来守卫这棵树。放在顶点 $x$ 的 takahashi 会守卫 $x$ 本身以及与 $x$ 通过一条边直接相连的顶点。 共有 $2^N$ 种选择放置 takahashi 的方式。其中有多少种方式会使得被一个或多个 takahashi 守卫的顶点恰好为 $K$ 个？ 对每个 $K=0,1,\ldots,N$，求出该计数并将其对 $(10^9+7)$ 取模后输出。

输入格式

输入按照下列格式由标准输入提供： $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

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

提示

$1 \leq N \leq 2000$ $1 \leq u_i \lt v_i \leq N$ 给定的图是一棵树。 输入中的所有数值均为整数。共有八种选择放置 takahashi 的方式，如下所示：

不在任何顶点放置 takahashi，守卫 0 个顶点。 在顶点 $1$ 放置 takahashi，守卫所有顶点。 在顶点 $2$ 放置 takahashi，守卫顶点 $1$ 和 $2$。 在顶点 $3$ 放置 takahashi，守卫顶点 $1$ 和 $3$。 在顶点 $1$ 和 $2$ 放置 takahashi，守卫所有顶点。 在顶点 $1$ 和 $3$ 放置 takahashi，守卫所有顶点。 在顶点 $2$ 和 $3$ 放置 takahashi，守卫所有顶点。 在所有顶点都放置 takahashi，守卫所有顶点。

标签: AtCoder|abc207F

来源

AtCoder|abc207F