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 \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.
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