← 返回题目列表

AtCoder · abc287_f

I. 组件

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

你有一棵树 N 顶点。 顶点已编号 1 通过 N,以及 i第一条边连接顶点 a_i 和顶点 b_i.

解决以下每个问题 x=1,2,\ldots,N:

  • 有 (2^N-1) 非空子集 树的顶点的 V 。 求模数 998244353,这样的 V 得出的子图 V 正是 x 连接的组件。
什么是归纳子图? 让 S 是图顶点的子集 G;那么子图 G 引起 S 是一个图,其顶点集为 S 且其边集由所有边组成 G 其两端都包含在 S.

约束

  • 1 \leq N \leq 5000
  • 1 \leq a_i \lt b_i \leq N
  • 给定的图是一棵树。

输入

输入由标准输入按以下格式给出:

N
a_1 b_1
\vdots
a_{N-1} b_{N-1}

输出

打印 N 行。
的 i- 第行应包含以下内容的答案 x=i.


示例输入 1

4
1 2
2 3
3 4

示例输出 1

10
5
0
0

归纳子图在以下五种情况下将有两个连通分量,在其他情况下有一个连通分量。

  • V = \{1,2,4\}
  • V = \{1,3\}
  • V = \{1,3,4\}
  • V = \{1,4\}
  • V = \{2,4\}

示例输入 2

2
1 2

示例输出 2

3
0

示例输入 3

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

示例输出 3

140
281
352
195
52
3
0
0
0
0