AT_abc264_h [ABC264Ex] Perfect Binary Tree

题目描述

有一棵包含 $N$ 个顶点的有根树，顶点编号为 $1,2,\dots,N$。
根为顶点 $1$，对于每个顶点 $i\ (\ge 2)$，其父节点为 $P_i\ (< i)$。
对于每个整数 $k=1,2,\dots,N$，请解答以下问题。

从编号为 $1$ 到 $k$ 的顶点中，选择若干个顶点（必须包含顶点 $1$）的方法共有 $2^{k-1}$ 种。
在这些选择方法中，有多少种方式使得所选顶点集合在原树中诱导出的子图的形状是以顶点 $1$ 为根的完全二叉树（即顶点数可以表示为 $2^d-1$ 的某个正整数 $d$）？
由于答案可能非常大，请输出对 $998244353$ 取模的结果。

什么是诱导子图？

对于某个图 $G$，选出一部分顶点组成集合 $S$。由 $S$ 诱导出的子图 $H$ 的构造如下：

• $H$ 的顶点集合与 $S$ 相同。
• 对于 $S$ 中的每一对顶点 $(i,j)$，如果 $G$ 中存在连接 $i$ 和 $j$ 的边，则在 $H$ 中也添加这条边。

什么是完全二叉树？

完全二叉树是满足以下所有条件的有根树：

• 除叶子节点外，每个节点恰好有 $2$ 个子节点。
• 所有叶子节点到根的距离相同。

此外，只有 $1$ 个顶点且没有边的图也视为完全二叉树。

输入格式

输入以如下格式从标准输入读入：

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

输出格式

输出 $N$ 行。第 $i$ 行输出 $k=i$ 时的答案，结果为整数。

输入输出样例 #1

输入 #1

10
1 1 2 1 2 5 5 5 1

输出 #1

1
1
2
2
4
4
4
5
7
10

输入输出样例 #2

输入 #2

1

输出 #2

1

输入输出样例 #3

输入 #3

10
1 2 3 4 5 6 7 8 9

输出 #3

1
1
1
1
1
1
1
1
1
1

输入输出样例 #4

输入 #4

13
1 1 1 2 2 2 3 3 3 4 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 < i$

样例解释 1

• 当 $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\}$ 是需要计数的顶点选择方式。

样例解释 2

当 $N=1$ 时，输入的第 2 行为空行。

由 ChatGPT 4.1 翻译