Treasure Hunting

题目描述

有一个以 $0$ 到 $N$ 编号的有根树，根为顶点 $0$，顶点 $i$ 的父节点是顶点 $p_i$。
在顶点 $1,2,\dots,N$ 中有一个顶点藏有宝藏。宝藏在顶点 $i$ 的概率是 $\frac{a_i}{\sum_{j=1}^N a_j}$。 此外，每个顶点有两种状态之一：“已搜索”和“未搜索”。初始时顶点 $0$ 为已搜索，其他所有顶点为未搜索。
在包含宝藏的顶点被标为已搜索之前，你执行以下操作：

选择一个父节点为已搜索的未搜索顶点，并将其标记为已搜索。

当你采取行动以最小化期望操作次数时，求所需的操作次数的期望值，对 $998244353$ 取模。 给定 $T$ 个测试用例；对每个测试用例求解。

输入格式

输入按下列格式由标准输入给出。这里，$\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

提示

$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$。 所有输入值均为整数。在第一个测试用例中，期望操作次数为 $\frac{13}{6}$。

标签: AtCoder|abc376G

来源

AtCoder|abc376G