[ABC264Ex] Perfect Binary Tree

我们有一颗以 $1$ 为根的有根树。 对于每一个 $2 \le i \le n$ 的 $i$，它的父亲是 $p_i$。 我们随机选一些编号在 $1$ 到 $k$ 的点，钦定节点 $1$ 一定被选中，一共有 $2^{k-1}$ 种选择方法。 现在芷萱姐姐想知道，当 $k=1,2,\cdots,N$ 时，有多少种选择方法，使得所选顶点的诱导子图是一颗以 $1$ 为根的完美二叉树（Perfect Binary Tree）。请输出答案对 $998244353$ 取模的结果。 + 输入的全都是整数 + $1 \le N \le 3\times 10^5$ + $1 \le p_i<i$ Translated by [Tx_Lcy](https://www.luogu.com.cn/user/253608)

[problemUrl]: https://atcoder.jp/contests/abc264/tasks/abc264_h 頂点に $ 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 $ についての答えを整数として出力せよ。

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 $ 行目は空行です。