← 返回题目列表

AtCoder · abc376_g

G. 寻宝

中文机器翻译题面 查看原题

分数: 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}.