题目描述

頂点に $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\ を満たす全ての頂点対\ (i,j)$ について、 $G$ 中に $i,j$ を結ぶ辺が存在すれば、 $H$ にも $i,j$ を結ぶ辺を追加する。

完全二分木とは? 完全二分木とは、以下の全ての条件を満たす根付き木です。 - 葉以外の全ての頂点が、ちょうど $2$ つの子を持つ。

• 全ての葉が根から等距離にある。

ただし、頂点が $1$ つで辺が $0$ 本のグラフも完全二分木であるものとします。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $P_2$ $P_3$ $\dots$ $P_N$

输出格式

$N$ 行出力せよ。 そのうち $i$ ( $1\ \le\ i\ \le\ N$ ) 行目には $k=i$ についての答えを整数として出力せよ。

题目大意

我们有一颗以 $1$ 为根的有根树。

对于每一个 $2 \le i \le n$ 的 $i$，它的父亲是 $p_i$。

我们随机选一些编号在 $1$ 到 $k$ 的点，钦定节点 $1$ 一定被选中，一共有 $2^{k-1}$ 种选择方法。

现在芷萱姐姐想知道有多少种选择方法，使得所选顶点的诱导子图是一颗以 $1$ 为根的满二叉树。

• 输入的全都是整数

• $1 \le N \le 10^5$

• $1 \le p_i<i$

Translated by Tx_Lcy

10
1 1 2 1 2 5 5 5 1

1
1
2
2
4
4
4
5
7
10

1

1

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

提示

制約

• 入力は全て整数
• $1\ \le\ N\ \le\ 3\ \times\ 10^5$
• $1\ \le\ P_i\ <\ i$

Sample Explanation 1

- $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\}$ が数えるべき頂点の選び方となります。

Sample Explanation 2

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