AT_abc269_h [ABC269Ex] Antichain

题目描述

有一棵包含 $N$ 个顶点的有根树 $T$，顶点编号为 $1$ 到 $N$。顶点 $1$ 是根节点，对于每个 $i$ $(2 \leq i \leq N)$，顶点 $i$ 的父节点为 $P_i$。

对于 $T$ 的顶点集合 $V = \{1, 2, \dots, N\}$ 的所有非空子集 $S$，如果满足以下条件，则称 $S$ 为良好顶点集合：

• 对于 $S$ 中任意不同的顶点对 $(u, v)$，$u$ 不是 $v$ 的祖先。

对于 $K = 1, 2, \dots, N$，请你求出（所有大小为 $K$ 的良好顶点集合的个数）对 $998244353$ 取模的结果。

输入格式

输入通过标准输入给出，格式如下：

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

输出格式

输出共 $N$ 行。第 $i$ 行输出 $K = i$ 时的答案。

输入输出样例 #1

输入 #1

4
1 2 1

输出 #1

4
2
0
0

输入输出样例 #2

输入 #2

6
1 1 2 2 5

输出 #2

6
6
2
0
0
0

输入输出样例 #3

输入 #3

6
1 1 1 1 1

输出 #3

6
10
10
5
1
0

输入输出样例 #4

输入 #4

10
1 2 1 2 1 1 2 6 9

输出 #4

10
30
47
38
16
3
0
0
0
0

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq P_i < i$
• 所有输入的值均为整数

样例解释 1

对于 $1 \leq K \leq N$，枚举所有大小为 $K$ 的良好顶点集合如下：

• $K=1$：$\{1\}$，$\{2\}$，$\{3\}$，$\{4\}$
• $K=2$：$\{2, 4\}$，$\{3, 4\}$
• $K=3,4$：不存在良好顶点集合。

由 ChatGPT 4.1 翻译