AT_abc207_f [ABC207F] Tree Patrolling

题目描述

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

你作为这棵树的主人，打算在若干个顶点（可以为 $0$ 个）上选择放置高桥君，让他来守卫这棵树。被放置在顶点 $x$ 的高桥君会守卫顶点 $x$ 以及所有与 $x$ 直接通过边相连的顶点。

选择放置高桥君的顶点的方式共有 $2^N$ 种。在这些方式中，有多少种方式使得被至少一位高桥君守卫的顶点恰好有 $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$ 时的答案。

输入输出样例 #1

输入 #1

3
1 3
1 2

输出 #1

1
0
2
5

输入输出样例 #2

输入 #2

5
1 3
4 5
1 5
2 3

输出 #2

1
0
2
5
7
17

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $1 \leq N \leq 2000$
• $1 \leq u_i < v_i \leq N$
• 给定的图为一棵树
• 输入均为整数

样例说明 1

放置高桥君的顶点选择方式共有如下 $8$ 种：

• 不在任何顶点放置高桥君。此时所有顶点都未被守卫。
• 只在顶点 $1$ 放置高桥君。此时所有顶点都被守卫。
• 只在顶点 $2$ 放置高桥君。此时顶点 $1$ 和 $2$ 共 $2$ 个顶点被守卫。
• 只在顶点 $3$ 放置高桥君。此时顶点 $1$ 和 $3$ 共 $2$ 个顶点被守卫。
• 在顶点 $1$ 和顶点 $2$ 放置高桥君。此时所有顶点都被守卫。
• 在顶点 $1$ 和顶点 $3$ 放置高桥君。此时所有顶点都被守卫。
• 在顶点 $2$ 和顶点 $3$ 放置高桥君。此时所有顶点都被守卫。
• 在所有顶点都放置高桥君。此时所有顶点都被守卫。

由 ChatGPT 4.1 翻译