寻宝

题目描述

有一棵以 $0$ 到 $N$ 编号的 $N+1$ 个顶点组成的有根树。顶点 $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 \le R \lt 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$ 个测试用例的答案。

样例

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

166374061
295776107
680203339

在第一个测试用例中,期望操作次数为 $\frac{13}{6}$。

数据范围

• $1 \le T \le 2 \times 10^5$
• $1 \le N \le 2 \times 10^5$
• $0 \le p_i \lt i$
• $1 \le a_i$
• $\sum_{i=1}^N a_i \le 10^8$
• 所有测试用例的 $N$ 之和不超过 $2 \times 10^5$。
• 所有输入值均为整数。