Score : $600$ points

问题描述

我们有一棵拥有 $N$ 个顶点的有根树，顶点编号为 $1,2,\dots,N$。
树以顶点 $1$ 为根，顶点 $i \geq 2$ 的父节点为顶点 $P_i(<i)$。
对于每个整数 $k=1,2,\dots,N$，解决以下问题：

从编号在 $1$ 到 $k$ 之间的顶点中选择一部分顶点的方式共有 $2^{k-1}$ 种，其中必须包含顶点 $1$。
其中有多少种方式满足以下条件：由所选顶点集合所诱导出的子图形成了一棵以顶点 $1$ 为根的完美二叉树（该二叉树拥有正整数 $d$ 时的 $2^d-1$ 个顶点）？
由于计数结果可能非常大，请输出模 $998244353$ 后的结果。

什么是诱导子图？

令 $S$ 为图 $G$ 的顶点集合的一个子集。由这个顶点集合 $S$ 所诱导出的子图 $H$ 是这样构建的：

• 将 $H$ 的顶点集合设为 $S$。

• 然后，按以下方式向 $H$ 添加边：

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

什么是完美二叉树？完美二叉树是一棵满足以下所有条件的有根树：

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

此处，我们也把含有 $1$ 个顶点和 $0$ 条边的图视为一棵完美二叉树。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

We have a rooted tree with $N$ vertices numbered $1,2,\dots,N$.
The tree is rooted at Vertex $1$, and the parent of Vertex $i \ge 2$ is Vertex $P_i(<i)$.
For each integer $k=1,2,\dots,N$, solve the following problem:

There are $2^{k-1}$ ways to choose some of the vertices numbered between $1$ and $k$ so that Vertex $1$ is chosen.
How many of them satisfy the following condition: the subgraph induced by the set of chosen vertices forms a perfect binary tree (with $2^d-1$ vertices for a positive integer $d$) rooted at Vertex $1$?
Since the count may be enormous, print the count modulo $998244353$.

What is an induced subgraph?

Let $S$ be a subset of the vertex set of a graph $G$. The subgraph $H$ induced by this vertex set $S$ is constructed as follows:

• Let the vertex set of $H$ equal $S$.

• Then, we add edges to $H$ as follows:

• For all vertex pairs $(i, j)$ such that $i,j \in S, i < j$, if there is an edge connecting $i$ and $j$ in $G$, then add an edge connecting $i$ and $j$ to $H$.

What is a perfect binary tree? A perfect binary tree is a rooted tree that satisfies all of the following conditions:

• Every vertex that is not a leaf has exactly $2$ children.
• All leaves have the same distance from the root.

Here, we regard a graph with $1$ vertex and $0$ edges as a perfect binary tree, too.

Constraints

• All values in input are integers.
• $1 \le N \le 3 \times 10^5$
• $1 \le P_i < i$

Input

Input is given from Standard Input in the following format:

$N$

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

Output

Print $N$ lines. The $i$-th ($1 \le i \le N$) line should contain the answer as an integer when $k=i$.

Sample Input 1

10
1 1 2 1 2 5 5 5 1

Sample Output 1

1
1
2
2
4
4
4
5
7
10

The following ways of choosing vertices should be counted:

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

Sample Input 2

1

Sample Output 2

1

If $N=1$, the $2$-nd line of the Input is empty.

Sample Input 3

10
1 2 3 4 5 6 7 8 9

Sample Output 3

1
1
1
1
1
1
1
1
1
1

Sample Input 4

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

Sample Output 4

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

update @ 2024/3/10 11:11:11