AT_pakencamp_2024_day2_e Excluded Children

頂点 $ 1 $ を根とする $ N $ 頂点の根付き木があり、頂点 $ i $ の親は $ P_i $ です。また、各頂点には $ 1 $ つの非負整数を書くことができます。 あなたは、まずこの木の全ての葉、すなわち子を $ 1 $ つも持たない頂点に $ 0 $ か $ 1 $ を書きます。その後、葉でない頂点全てに対し、その子の頂点に書かれた数の集合の $ \mathrm{mex} $ を書きます。 厳密には、頂点 $ v $ に書く非負整数を $ A_v $ としたとき、以下の条件を満たすようにします。 - 頂点 $ v $ が葉のとき、 $ A_v = 0 $ または $ A_v = 1 $ - 頂点 $ v $ が葉でないとき、頂点 $ v $ の子を $ C_1,C_2,\ldots,C_M $ とすると、 $ A_v = \mathrm{mex}(\{A_{C_1},A_{C_2},\ldots,A_{C_M}\}) $ ただし、ある非負整数の集合 $ S $ に対し、 $ \mathrm{mex}(S) $ は $ S $ に含まれない最小の非負整数を表します。 葉の個数を $ L $ とすると、頂点への非負整数の書き方は $ 2^L $ 通りあります。 $ k = 0,1,2,\ldots,N $ のそれぞれについて、 $ 2^L $ 通りの書き方の中で最終的に頂点 $ 1 $ に $ k $ が書かれるようなものの個数を $ 998244353 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ P_2 $ $ P_3 $ $ \ldots $ $ P_N $

$ N+1 $ 行出力してください。 $ i $ 行目 $ (0 \leq i \leq N) $ には、最終的に頂点 $ 1 $ に $ i $ が書かれるような葉の頂点への数の書き方の個数を $ 998244353 $ で割った余りを出力してください。

### 小課題 1. ( $ 4 $ 点) 葉の個数は $ 5 $ 個以下 2. ( $ 8 $ 点) $ P_i = 1 $ ( $ 2 \leq i \leq N $ ) 3. ( $ 8 $ 点) $ P_i = \lfloor \frac{i}{2} \rfloor $ ( $ 2 \leq i \leq N $ ) 4. ( $ 15 $ 点) $ N \leq 100 $ 5. ( $ 25 $ 点) $ N \leq 5000 $ 6. ( $ 40 $ 点) 追加の制約はない ### Sample Explanation 1 この入力例では、葉は頂点 $ 3, 4, 5 $ です。例えば、これらにそれぞれ $ 0, 1, 0 $ を書いた場合、 - 頂点 $ 2 $ の子は 頂点 $ 4, 5 $ で、それぞれ $ 1, 0 $ が書かれているため、頂点 $ 2 $ には $ \mathrm{mex}(\{0,1\}) = 2 $ を書きます。 - 頂点 $ 1 $ の子は 頂点 $ 2, 3 $ で、それぞれ $ 2, 0 $ が書かれているため、頂点 $ 1 $ には $ \mathrm{mex}(\{0,2\}) = 1 $ を書きます。 よって、この場合頂点 $ 1 $ に書かれる数は $ 1 $ です。 このサンプルは小課題 $ 1,3,4,5,6 $ を満たします。 ### Sample Explanation 2 このサンプルは小課題 $ 1,4,5,6 $ を満たします。 ### Constraints - $ 1 \leq N \leq 2 \times 10^{5} $ - $ 1 \leq P_i < i $ ( $ 2 \leq i \leq N $ ) - 入力は全て整数