配点 : 100 点
問題文
頂点 1 植根于 N 我有一棵有根的顶点树,并且顶点 i 的父级是 P_i 。另外,每个顶点都有 您可以写入 1 非负整数。
您必须首先移除这棵树的所有叶子或子节点。 1 到没有任何顶点 写入 0 或 1 。那么,对于所有非叶顶点,写在其子顶点上的数字集是 \mathrm{mex} 。
严格来说,顶点 在 v 中写入一个非负整数 A_v ,请确保满足以下条件。 当
- 頂点 v 是一片叶子时, 当A_v = 0 或 至少 A_v = 1
- 頂点 v 不是叶子时,顶点 v 的孩子 C_1,C_2,\ldots,C_M 以 A_v = \mathrm{mex}(\{A_{C_1},A_{C_2},\ldots,A_{C_M}\})
然而,某组非负整数 S , 您可以获得 \mathrm{mex}(S) 是 您也可以写 S 中不包含的最小非负整数。 您将获得
叶子数量 L ,那么向顶点写入非负整数的方法是 对于每个 2^L 方法有很多。k = 0,1,2,\ldots,N , 2^L 写法的最后一点 写入 1 至 该值是 k 的对象数量为 998244353 除以求余。
制約
- 1 \leq N \leq 2 \times 10^{5}
- 1 \leq P_i < i (2 \leq i \leq N)
- 所有输入均为整数
小課題
- (4 点)叶子的数量是 5 個以下
- (8 点) P_i = 1 (2 \leq i \leq N)
- (8 点) P_i = \lfloor \frac{i}{2} \rfloor (2 \leq i \leq N)
- (15 点) N \leq 100
- (25 点) N \leq 5000
- (40 点)无附加约束 打印第
入力
输入是按以下格式从标准输入给出的。
N P_2 P_3 \ldots P_N
出力
N+1 行。 列出 i 行目 (0 \leq i \leq N) 终于有了一个顶点 计算在叶子的顶点处写入数字的方式的数量,以便写入 1 至 该值是 i 。 998244353 后的余数。
入力例 1
5 1 1 2 2
出力例 1
3 3 2 0 0 0
在此示例输入中,叶子是顶点 3, 4, 5 。例如,这些中的每一个 如果你写 0, 1, 0 ,
- 頂点 2 的子级是顶点 分别为 4, 5 所以,每个 1, 0 被写入,所以顶点 2 有 直到 \mathrm{mex}(\{0,1\}) = 2 。
- 頂点 1 的子级是顶点 分别为 2, 3 所以,每个 2, 0 被写入,所以顶点 1 有 直到 \mathrm{mex}(\{0,2\}) = 1 。
因此,在这种情况下顶点 1 中写入的数字是 1 。
此示例是一个小作业。 1,3,4,5,6 满足…
入力例 2
9 1 2 2 1 2 3 2 5
出力例 2
15 15 2 0 0 0 0 0 0 0
此示例是一个小作业。 1,4,5,6 满足…