AT_abc376_g [ABC376G] Treasure Hunting

题目描述

有一棵有 $N+1$ 个顶点的有根树，顶点编号为 $0$ 到 $N$。顶点 $0$ 是根，顶点 $i$ 的父节点是顶点 $p_i$。
在顶点 $1$、顶点 $2$、$\dots$、顶点 $N$ 中的某一个顶点藏有宝物。顶点 $i$ 藏有宝物的概率为 $\frac{a_i}{\sum_{j=1}^N a_j}$。
此外，每个顶点有“已探索”和“未探索”两种状态。初始时，顶点 $0$ 为已探索，其余顶点均为未探索。
你需要进行如下操作，直到藏有宝物的顶点变为已探索：

• 选择一个父节点已探索的未探索顶点，将其状态变为已探索。

请在操作次数的期望值最小的情况下，求出操作次数的期望值，并对 $998244353$ 取模。

给定 $T$ 组测试数据，请分别输出每组的答案。

期望值 $\bmod\ 998244353$ 的定义：
可以证明，所求期望值一定是有理数。在本题的约束下，若将其表示为最简分数 $\frac{P}{Q}$，则 $Q \not\equiv 0 \pmod{998244353}$ 也成立。此时，存在唯一的整数 $R$ 满足 $R \times Q \equiv P \pmod{998244353},\ 0 \leq R < 998244353$。请输出这个 $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

输入 #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 \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$
• 输入的所有数均为整数

样例解释 1

第 $1$ 个测试用例中，操作次数的期望值为 $\frac{13}{6}$。

由 ChatGPT 4.1 翻译