/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 650 点
問題文
頂点に 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 を答えてください。
制約
- 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 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。ここで \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
3 3 0 0 1 1 2 3 5 0 1 0 0 0 8 6 5 1 7 10 0 1 1 3 3 1 4 7 5 4 43 39 79 48 92 90 76 30 16 30
出力例 1
166374061 295776107 680203339
1 番目のテストケースにおける操作回数の期待値は \frac{13}{6} です。
Score : 650 points
Problem Statement
There is a rooted tree with N + 1 vertices numbered from 0 to N. Vertex 0 is the root, and the parent of vertex i is vertex p_i.
One of the vertices among vertex 1, vertex 2, ..., vertex N hides a treasure. The probability that the treasure is at vertex i is \frac{a_i}{\sum_{j=1}^N a_j}.
Also, each vertex is in one of the two states: "searched" and "unsearched". Initially, vertex 0 is searched, and all other vertices are unsearched.
Until the vertex containing the treasure becomes searched, you perform the following operation:
- Choose an unsearched vertex whose parent is searched, and mark it as searched.
Find the expected number of operations required when you act to minimize the expected number of operations, modulo 998244353.
You are given T test cases; solve each of them.
How to find an expected value modulo 998244353
It can be proved that the expected value is always a rational number. Under the constraints of this problem, it can also be proved that when the expected value is expressed as an irreducible fraction \frac{P}{Q}, we have Q \not\equiv 0 \pmod{998244353}. In this case, there is a unique integer R satisfying R \times Q \equiv P \pmod{998244353},\ 0 \leq R < 998244353. Report this R.
Constraints
- 1 \leq T \leq 2 \times 10^5
- 1 \leq N \leq 2 \times 10^5
- 0 \leq p_i < i
- 1 \leq a_i
- \sum_{i=1}^N a_i \leq 10^8
- The sum of N over all test cases is at most 2 \times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format. Here, \mathrm{case}_i denotes the i-th test case.
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case is given in the following format:
N p_1 p_2 \dots p_N a_1 a_2 \dots a_N
Output
Print T lines. The i-th line should contain the answer for the i-th test case.
Sample Input 1
3 3 0 0 1 1 2 3 5 0 1 0 0 0 8 6 5 1 7 10 0 1 1 3 3 1 4 7 5 4 43 39 79 48 92 90 76 30 16 30
Sample Output 1
166374061 295776107 680203339
In the first test case, the expected number of operations is \frac{13}{6}.