← 返回题目列表

AtCoder · abc264_h

Ex. 完美二叉树

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

我们有一棵有根树 N 顶点编号 1,2,\dots,N.
树的根位于顶点 1,以及 Vertex 的父级 i \ge 2 是顶点 P_i(<i).
对于每个整数 k=1,2,\dots,N,解决以下问题:

有 2^{k-1} 选择编号之间的一些顶点的方法 1 和 k 这样顶点 选择 1 。
其中有多少满足以下条件:由所选顶点集导出的子图形成完美二叉树( 2^d-1 正整数的顶点 d) 植根于 Vertex 1?
由于计数可能很大,因此打印计数模数 998244353.

什么是诱导子图?

让 S 是图的顶点集的子集 G。 子图 H 由该顶点集引起 S 的构造如下:

  • 设顶点集 H 等于 S.
  • 然后,我们添加边 H 如下:
    • 对于所有顶点对 (i, j) 这样 i,j \in S, i < j,如果有一条边连接 i 和 j in G,然后添加一条边连接 i 和 j to H.
什么是完美二叉树? 完美二叉树是满足以下所有条件的有根树:
  • 每个不是叶子的顶点都有 2 孩子们。
  • 所有叶子到根的距离都相同。
在这里,我们将图视为 1 顶点和 0 的边也是完美二叉树。

约束

  • 输入中的所有值都是整数。
  • 1 \le N \le 3 \times 10^5
  • 1 \le P_i < i

输入

输入由标准输入按以下格式给出:

N
P_2 P_3 \dots P_N

输出

打印 N 行。 的 i-th (1 \le i \le N) 行应包含整数答案 k=i.


示例输入 1

10
1 1 2 1 2 5 5 5 1

示例输出 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

示例输入 2

1

示例输出 2

1

If N=1, 2- 输入的第 2 行为空。


示例输入 3

10
1 2 3 4 5 6 7 8 9

示例输出 3

1
1
1
1
1
1
1
1
1
1

示例输入 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