Ex - Perfect Binary Tree
当前没有测试数据。
Ex - 完全二叉树
分数：$600$ 分
问题描述
我们有一棵有 $N$ 个顶点的根树，编号为 $1,2,\dots,N$。
该树以顶点 $1$ 为根，顶点 $i \ge 2$ 的父节点为顶点 $P_i(<i)$。
对于每个整数 $k=1,2,\dots,N$，解决以下问题：
有 $2^{k-1}$ 种方法可以选择位于 $1$ 到 $k$ 之间编号的一些顶点，使得选中了顶点 $1$。
其中有多少种方法满足下列条件：选中的顶点集合构成以顶点 $1$ 为根的完全二叉树（其中 $d$ 为正整数，顶点数为 $2^d-1$）？
由于计数可能非常大，所以将计数结果对 $998244353$ 取模后输出。
什么是诱导子图？
设 $S$ 是一个图 $G$ 的顶点集的子集。由子集 $S$ 所诱导的子图 $H$ 的构造步骤如下：
- 令子图 $H$ 的顶点集等于 $S$。
- 然后，我们根据以下规则添加边：
- 对于所有满足 $i,j \in S, i < j$ 的顶点对 $(i, j)$，如果图 $G$ 中连接了 $i$ 和 $j$ 的边，则在子图 $H$ 中也连接 $i$ 和 $j$。
什么是完全二叉树？
满足下列条件的根树称为完全二叉树：
- 非叶节点恰好有 $2$ 个孩子。
- 所有叶子与根节点的距离相等。
在此定义下，一个顶点数为 ，边数为 的图也被视为完全二叉树。
约束
- 输入中的所有值均为整数。
- $1 \le N \le 3 \times 10^5$
- $1 \le P_i < i$
输入
从标准输入中以以下格式给出：
输出
输出 $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
以下选择顶点的方式应计数：
- 当 $k \ge 1$ 时，$\{1\}$
- 当 $k \ge 3$ 时，$\{1,2,3\}$
- 当 $k \ge 5$ 时，$\{1,2,5\},\{1,3,5\}$
- 当 $k \ge 8$ 时，$\{1,2,4,5,6,7,8\}$
- 当 $k \ge 9$ 时，$\{1,2,4,5,6,7,9\},\{1,2,4,5,6,8,9\}$
- 当 $k = 10$ 时，$\{1,2,10\},\{1,3,10\},\{1,5,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