配点 : $600$ 点

問題文

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

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

制約

• 入力は全て整数
• $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$ についての答えを整数として出力せよ。

10
1 1 2 1 2 5 5 5 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\}$

が数えるべき頂点の選び方となります。

1

1

$N=1$ である場合、入力の $2$ 行目は空行です。

10
1 2 3 4 5 6 7 8 9

1
1
1
1
1
1
1
1
1
1

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

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