分数: 600 点
问题陈述
你有一棵树 N 顶点,编号 1 通过 N。的 i第一条边连接顶点 u_i 和顶点 v_i.
您将选择一些顶点(可能没有)并在每个顶点中放置一个高桥来保护树。放置在 Vertex 的高桥 x 将守护 x 本身和直接连接到的顶点 x 的边缘。
有 2^N 选择放置高桥顶点的方法。其中到底有多少个 K 顶点由一个或多个高桥守护?
找到这个计数并打印它的模数 (10^9+7) 对于每个 K=0,1,\ldots,N.
约束
- 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
有八种方式选择放置高桥的顶点,如下:
- 在没有顶点处放置高桥,不保护任何顶点。
- 在顶点放置高桥 1,保护所有顶点。
- 在顶点放置高桥 2,保护顶点 1 和 2.
- 在顶点放置高桥 3,保护顶点 1 和 3.
- 在顶点处放置高桥 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