分数: 650 点
问题陈述
有一棵有根的树 N + 1 顶点编号自 0 to N。顶点 0 是根,也是顶点的父级 i 是顶点 p_i.
顶点中的顶点之一 1,顶点 2, ..., 顶点 N 隐藏着宝藏。宝藏位于顶点的概率 i is \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}.