102697: [AtCoder]ABC269 Ex - Antichain

Problem Statement

We have a rooted tree $T$ with $N$ vertices numbered $1$ to $N$. Vertex $1$ is the root, and the parent of vertex $i$ $(2 \leq i \leq N)$ is vertex $P_i$.

A non-empty subset $S$ of the vertex set $V = \lbrace 1, 2,\dots, N\rbrace$ of $T$ is said to be a good vertex set when it satisfies the following condition.

• For every pair of different vertices $(u, v)$ in $S$, the following holds: $u$ is not an ancestor of $v$.

For each $K = 1, 2, \dots, N$, find the number, modulo $998244353$, of good vertex sets with exactly $K$ vertices.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq P_i \lt i$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$N$
$P_2$ $P_3$ $\dots$ $P_N$

Output

Print $N$ lines. The $i$-th line should contain the answer for $K = i$.

Sample Input 1

4
1 2 1

Sample Output 1

4
2
0
0

For each $1 \leq K \leq N$, the good vertex sets of size $K$ are listed below.

• $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$: There is none.

Sample Input 2

6
1 1 2 2 5

Sample Output 2

6
6
2
0
0
0

Sample Input 3

6
1 1 1 1 1

Sample Output 3

6
10
10
5
1
0

Sample Input 4

10
1 2 1 2 1 1 2 6 9

Sample Output 4

10
30
47
38
16
3
0
0
0
0

问题描述

我们有一个有根树$T$，有$N$个顶点，编号为$1$到$N$。顶点$1$是根，顶点$i$ $(2 \leq i \leq N)$的父顶点是顶点$P_i$。

顶点集$V = \lbrace 1, 2,\dots, N\rbrace$中的非空子集$S$被认为是 好的顶点集 ，当它满足以下条件时。

• 对于$S$中的每一对不同的顶点$(u, v)$，满足以下条件：$u$不是$v$的祖先。

对于每个$K = 1, 2, \dots, N$，找出有正好$K$个顶点的良好顶点集的数量，对$998244353$取模。

约束

• $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