分数: 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