← 返回题目列表

AtCoder · abc269_h

Ex. 反链

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

分数: 600 点

问题陈述

我们有一棵有根的树 T 与 N 顶点编号 1 to N。顶点 1 是根,也是顶点的父级 i (2 \leq i \leq N) 是顶点 P_i.

非空子集 顶点集的 S 顶点集的 V = \lbrace 1, 2,\dots, N\rbrace of T 据说是 良好的顶点集 当满足以下条件时。

  • 对于每对不同的顶点 (u, v) in S,以下成立: u 不是 v.

对于每个 K = 1, 2, \dots, N,求模数 998244353,良好的顶点集与 K 顶点。

约束

  • 2 \leq N \leq 2 \times 10^5
  • 1 \leq P_i \lt i
  • 输入中的所有值都是整数。

输入

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

N
P_2 P_3 \dots P_N

输出

打印 N 行。的 i- 第行应包含以下问题的答案 K = i.


示例输入 1

4
1 2 1

示例输出 1

4
2
0
0

对于每个 1 \leq K \leq N,好的顶点集大小 下面列出了 K 。

  • K=1: \lbrace 1 \rbrace, \lbrace 2 \rbrace, \lbrace 3 \rbrace, \lbrace 4 \rbrace.
  • K=2: \lbrace 2, 4 \rbrace, \lbrace 3, 4 \rbrace.
  • K=3,4:没有。

示例输入 2

6
1 1 2 2 5

示例输出 2

6
6
2
0
0
0

示例输入 3

6
1 1 1 1 1

示例输出 3

6
10
10
5
1
0

示例输入 4

10
1 2 1 2 1 1 2 6 9

示例输出 4

10
30
47
38
16
3
0
0
0
0