分数: 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 \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