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 \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 翻译