完美二叉树

题目描述

有一棵包含 $N$ 个顶点、编号为 $1, 2, \dots, N$ 的有根树。

树的根为顶点 $1$,顶点 $i \ge 2$ 的父亲为顶点 $P_i(\lt i)$。

对于每个整数 $k = 1, 2, \dots, N$,解决以下问题:

从编号在 $1$ 到 $k$ 之间的顶点中选择一部分,使得顶点 $1$ 被选中,共有 $2^{k-1}$ 种选法。

其中满足以下条件的有多少种:被选中的顶点集合导出的子图构成一棵以顶点 $1$ 为根、顶点数为 $2^d-1$($d$ 为正整数)的完美二叉树?

由于答案可能很大,请输出其对 $998244353$ 取模后的结果。

什么是导出子图?

设 $S$ 是图 $G$ 的顶点集的子集。由顶点集 $S$ 导出的子图 $H$ 按如下方式构造:

• 令 $H$ 的顶点集为 $S$。

然后按如下方式向 $H$ 中添加边:

• 对于所有满足 $i, j \in S, i \lt j$ 的顶点对 $(i, j)$,如果 $G$ 中存在连接 $i$ 和 $j$ 的边,则在 $H$ 中添加连接 $i$ 和 $j$ 的边。

什么是完美二叉树?

完美二叉树是满足以下所有条件的有根树:

• 每个不是叶子的顶点恰好有 $2$ 个孩子。
• 所有叶子到根的距离相同。

这里,由 $1$ 个顶点、$0$ 条边构成的图也视为完美二叉树。

输入格式

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

输出格式

输出 $N$ 行。

第 $i$ 行($1 \le i \le N$)应输出 $k=i$ 时的答案(一个整数)。

样例

10
1 1 2 1 2 5 5 5 1

1
1
2
2
4
4
4
5
7
10

应计入的选法如下:

• $\{1\}$,当 $k \ge 1$ 时
• $\{1,2,3\}$,当 $k \ge 3$ 时
• $\{1,2,5\},\{1,3,5\}$,当 $k \ge 5$ 时
• $\{1,2,4,5,6,7,8\}$,当 $k \ge 8$ 时
• $\{1,2,4,5,6,7,9\},\{1,2,4,5,6,8,9\}$,当 $k \ge 9$ 时
• $\{1,2,10\},\{1,3,10\},\{1,5,10\}$,当 $k = 10$ 时

1

1

若 $N=1$,输入的第 $2$ 行为空。

10
1 2 3 4 5 6 7 8 9

1
1
1
1
1
1
1
1
1
1

13
1 1 1 2 2 2 3 3 3 4 4 4

1
1
2
4
4
4
4
4
7
13
13
19
31

数据范围

• 输入中的所有值均为整数。
• $1 \le N \le 3 \times 10^5$
• $1 \le P_i \lt i$