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