103766: [Atcoder]ABC376 G - Treasure Hunting
Description
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 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}$.
Output
得分：650分
问题陈述
有一个有根树，包含$N + 1$个顶点，编号从0到$N$。顶点0是根，顶点$i$的父顶点是顶点$p_i$。
在顶点1、顶点2、...、顶点$N$中有一个顶点隐藏着宝藏。宝藏位于顶点$i$的概率是$\frac{a_i}{\sum_{j=1}^N a_j}$。
每个顶点都处于两种状态之一："已搜索"和"未搜索"。最初，顶点0是已搜索的，所有其他顶点都是未搜索的。
直到包含宝藏的顶点变为已搜索，执行以下操作：
- 选择一个未搜索的顶点，其父顶点是已搜索的，并将其标记为已搜索。
找出在操作以最小化操作次数的情况下所需的预期操作次数，模$998244353$。
你有$T$个测试用例；解决每一个。
如何找到模$998244353$的预期值
可以证明预期值总是一个有理数。在这个问题的约束下，也可以证明当预期值表示为一个不可约分数$\frac{P}{Q}$时，我们有$Q \not\equiv 0 \pmod{998244353}$。在这种情况下，存在一个唯一的整数$R$满足$R \times Q \equiv P \pmod{998244353},\ 0 \leq R < 998244353$。报告这个$R$。
约束条件
- $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$
- 所有测试用例的$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
在第一个测试用例中，预期操作次数是$\frac{13}{6}$。