AT_abc376_g [ABC376G] Treasure Hunting

[problemUrl]: https://atcoder.jp/contests/abc376/tasks/abc376_g 頂点に $ 0 $ から $ N $ までの番号がついた $ N\ +\ 1 $ 頂点の根付き木があります。頂点 $ 0 $ は根で、頂点 $ i $ の親は頂点 $ p_i $ です。 頂点 $ 1 $, 頂点 $ 2 $, $ \dots $, 頂点 $ N $ のうちどこか $ 1 $ 頂点に宝が隠されています。頂点 $ i $ に宝がある確率は $ \frac{a_i}{\sum_{j=1}^N\ a_j} $ です。 また、各頂点には「探索済」と「未探索」のどちらか一方の状態を持ちます。はじめ頂点 $ 0 $ は探索済で、それ以外の頂点は未探索です。 あなたは、宝がある頂点が探索済になるまで以下の操作を行います。 - 親が探索済であるような未探索の頂点を選び、その頂点を探索済にする。 操作回数の期待値が最小になるように行動した時の操作回数の期待値を $ \text{mod\ }998244353 $ で求めてください。 $ T $ 個のテストケースが与えられるので、それぞれに対して答えを求めてください。 期待値 $ \text{mod\ }{998244353} $ の定義 求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 $ \frac{P}{Q} $ で表した時、$ Q\ \not\ \equiv\ 0\ \pmod{998244353} $ となることも証明できます。このとき、$ R\ \times\ Q\ \equiv\ P\ \pmod{998244353},\ 0\ \leq\ R\ \lt\ 998244353 $ を満たす整数 $ R $ が一意に定まります。この $ R $ を答えてください。

入力は以下の形式で標準入力から与えられる。ここで $ \mathrm{case}_i $ は $ i $ 番目のテストケースを意味する。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ p_1 $ $ p_2 $ $ \dots $ $ p_N $ $ a_1 $ $ a_2 $ $ \dots $ $ a_N $

$ T $ 行出力せよ。$ i $ 行目には $ i $ 番目のテストケースの答えを出力せよ。

### 制約 - $ 1\ \leq\ T\ \leq\ 2\ \times\ 10^5 $ - $ 1\ \leq\ N\ \leq\ 2\ \times\ 10^5 $ - $ 0\ \leq\ p_i\ \lt\ i $ - $ 1\ \leq\ a_i $ - $ \sum_{i=1}^N\ a_i\ \leq\ 10^8 $ - 全てのテストケースに対する $ N $ の総和は $ 2\ \times\ 10^5 $ 以下 - 入力される値は全て整数 ### Sample Explanation 1 $ 1 $ 番目のテストケースにおける操作回数の期待値は $ \frac{13}{6} $ です。