Ex - Perfect Binary Tree Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

頂点に 1,2,\dots,N の番号が付いた、 N 頂点の根付き木があります。
根は頂点 1 であり、頂点 i \ge 2 について、その親は P_i(<i) です。
整数 k=1,2,\dots,N に対し次の問題を解いてください。

番号が 1 以上 k 以下の頂点を、頂点 1 を含むようにいくつか選ぶ方法は 2^{k-1} 通りあります。
そのうち、選ばれた頂点集合から誘導される部分グラフの形状が頂点 1 を根とする (頂点数がある正整数 d を用いて 2^d-1 と表せるような) 完全二分木になるような頂点の選び方はいくつですか?
答えは非常に大きくなる場合があるので、998244353 で割った余りを求めてください。

誘導される部分グラフとは?

あるグラフ G から、一部の頂点を選んだ集合を S とします。この頂点集合 S から誘導される部分グラフ H は以下のように構成されます。

  • H の頂点集合は S と一致させます。
  • その後、 H に以下のように辺を追加します。
    • i,j \in S, i < j を満たす全ての頂点対 (i,j) について、 G 中に i,j を結ぶ辺が存在すれば、 H にも i,j を結ぶ辺を追加する。
完全二分木とは? 完全二分木とは、以下の全ての条件を満たす根付き木です。
  • 葉以外の全ての頂点が、ちょうど 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 ( 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
  • 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

1

出力例 2

1

N=1 である場合、入力の 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

Score : 600 points

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