题目描述

有 $N$ 个事件，编号为 $1$ 到 $N$。每个事件的发生概率依赖于恰好另一个事件（称为父事件）的发生，但事件 $1$ 除外，它是一个独立事件。换句话说，对于每个事件 $i$（$2 \le i \le N$），给定三个值：$P_i$ 表示事件 $i$ 的父事件，$A_i$ 表示当父事件发生时事件 $i$ 发生的概率，$B_i$ 表示当父事件不发生时事件 $i$ 发生的概率。对于事件 $1$，其发生概率 $K$ 已给出。我们需要回答 $Q$ 个查询。每个查询包含两个不同的事件 $u_j$ 和 $v_j$，你需要求出事件 $u_j$ 和 $v_j$ 同时发生的概率。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含两个整数 $N$ 和 $Q$，分别表示事件的数量和查询的数量。接下来 $N$ 行描述每个事件。第一行包含一个整数 $K$，表示事件 $1$ 的发生概率乘以 $10^6$。接下来的 $N-1$ 行，每行包含三个整数 $P_i$、$A_i$ 和 $B_i$，分别表示事件 $i$ 的父事件、当父事件发生时事件 $i$ 的发生概率乘以 $10^6$，以及当父事件不发生时事件 $i$ 的发生概率乘以 $10^6$。然后，有 $Q$ 行描述查询，每行包含两个不同的整数 $u_j$ 和 $v_j$。对于每个查询，求出事件 $u_j$ 和 $v_j$ 同时发生的概率。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: R1 R2 R3 ... RQ，其中 $x$ 是测试用例编号（从 $1$ 开始），$R_j$ 是为第 $j$ 个查询计算出的概率对 $10^9 + 7$ 取模的结果，其精确定义如下。将第 $j$ 个查询的答案表示为最简分数 $\frac{p}{q}$，则 $R_j$ 必须满足模方程 $R_j \times q \equiv p \pmod{10^9 + 7}$，且 $0 \le R_j \le 10^9 + 6$。可以证明，在本问题的限制下，这样的 $R_j$ 总是存在且唯一确定。

2
5 2
200000
1 400000 300000
2 500000 200000
1 800000 100000
4 200000 400000
1 5
3 5
4 2
300000
1 100000 100000
2 300000 400000
3 500000 600000
1 2
2 4

Case #1: 136000001 556640004
Case #2: 710000005 849000006

提示

对于样例 #1，第一个查询：事件 $1$ 和 $5$ 同时发生的概率为（事件 $1$ 发生的概率）$\times$（在事件 $1$ 发生的条件下事件 $5$ 发生的概率）。事件 $1$ 发生的概率为 $0.2$。已知事件 $1$ 发生，事件 $4$ 发生的概率为 $0.8$。因此，在事件 $1$ 发生的条件下事件 $5$ 发生的概率为 $0.2 \times 0.8 + 0.4 \times 0.2 = 0.24$（事件 $4$ 发生时事件 $5$ 发生的概率加上事件 $4$ 不发生时事件 $5$ 发生的概率）。事件 $1$ 和 $5$ 同时发生的概率为 $0.2 \times 0.24 = 0.048$。答案 $0.048$ 可化为分数 $\frac{6}{125}$，可以验证 $136000001$ 满足输出部分所述的条件：$136000001 \times 125 \equiv 6 \pmod{10^9 + 7}$，且唯一确定。第二个查询：事件 $5$ 和 $3$ 同时发生的概率为 $0.10352$。

对于样例 #2，第一个查询：事件 $1$ 和 $2$ 同时发生的概率为（事件 $1$ 发生的概率）$\times$（在事件 $1$ 发生的条件下事件 $2$ 发生的概率）。由于 $1$ 是事件 $2$ 的父事件，给定事件 $1$ 发生时事件 $2$ 发生的概率即为 $A_2 = 0.1$。因此，事件 $1$ 和 $2$ 同时发生的概率为 $0.3 \times 0.1 = 0.03$。输出为 $3 \times 10^{-2} \bmod (10^9 + 7) = 710000005$。第二个查询：事件 $2$ 和 $4$ 同时发生的概率为 $0.057$。

限制条件

$1 \le T \le 100$。

对于每个 $i$ 从 $2$ 到 $N$，$1 \le P_i < i$。

对于所有 $j$，$1 \le u_j, v_j \le N$ 且 $u_j \ne v_j$。

对于每个 $i$ 从 $2$ 到 $N$，$0 \le A_i \le 10^6$。

对于每个 $i$ 从 $2$ 到 $N$，$0 \le B_i \le 10^6$。

$0 \le K \le 10^6$。

测试集 1

$2 \le N \le 1000$。

$1 \le Q \le 1000$。

测试集 2

最多 $5$ 个测试用例满足：

$2 \le N \le 2 \times 10^5$。

$1 \le Q \le 2 \times 10^5$。

其余测试用例满足：

$2 \le N \le 1000$。

$1 \le Q \le 1000$。

翻译由 DeepSeek V4 Pro 完成