[AdditionalFile5370.zip](file://AdditionalFile5370.zip?type=additional_file)

#5370. 「OOI 2023 Day 1」汽油价格

标签: 传统 | 时间限制: 3500 ms | 内存限制: 1024 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2023 Day1 T2 「Цены на бензин」。

伯利兰迪亚是一个庞大的国家，包含 $n$ 个城市。伯利兰迪亚的道路网络可以看作一棵有根树，总共有 $n - 1$ 条道路，从任意城市到另一城市有且仅有一条路径，且不会重复经过同一城市。为了便于描述国家结构，对于每个城市 $i$，固定了一个城市 $p_i$，表示从城市 $i$ 前往城市 $1$ 时需要首先到达的城市。换句话说，如果将树以城市 $1$ 为根，$p_i$ 即为城市 $i$ 的直接父节点。

伯利兰迪亚的每个城市都有一座加油站。这些加油站的定价方式很特别，每座加油站都有一个固定的价格范围，愿意在这个范围内销售汽油。城市 $i$ 的加油站愿意以任何价格从 $l_i$ 到 $r_i$（包含边界）出售汽油。

伯利兰迪亚的国王是个模范的家庭人，在 $m$ 年内，他每年都会有两个儿子出生。国王的孩子从小就参与国家事务，每年年底他们会检查汽油价格的公平性。从出生开始，在第 $i$ 年出生的国王孩子分别负责检查从城市 $a_i$ 到城市 $b_i$ 和从城市 $c_i$ 到城市 $d_i$ 的路径上的汽油价格。

检查过程如下：两个孩子同时分别从城市 $a_i$ 和 $c_i$ 开始他们的旅程。第 $i$ 年出生的第一个儿子沿着从城市 $a_i$ 到城市 $b_i$ 的路径前进，第二个儿子沿着从城市 $c_i$ 到城市 $d_i$ 的路径前进。他们会检查城市 $a_i$ 的汽油价格是否与城市 $c_i$ 的价格一致；接着检查从 $a_i$ 到 $b_i$ 路径上的第二个城市与从 $c_i$ 到 $d_i$ 路径上的第二个城市的汽油价格是否一致；以此类推，直到检查城市 $b_i$ 和 $d_i$ 的价格是否一致。保证从城市 $a_i$ 到 $b_i$ 的路径长度与从城市 $c_i$ 到 $d_i$ 的路径长度相等。

加油站必须严格遵守法律，因此所有汽油价格的检查都不能发现违规行为。请帮助伯利兰迪亚的加油站计算，在 $m$ 年内他们有多少种方式可以设定汽油价格。换句话说，对于从 $1$ 到 $m$ 的每个 $i$，计算在所有加油站设定汽油价格的方式数量，使得在第 $i$ 年及之前的孩子们进行检查时没有发现违规，并且每个加油站的价格都在其允许范围内。由于方式数量可能很大，请将答案对 $10^{9} + 7$ 取模。

输入格式

第一行包含一个整数 $n$ $(1 \le n \le 200000)$，表示伯利兰迪亚的城市数量。

第二行包含 $n - 1$ 个整数 $p_2, p_3, p_4, \ldots, p_n$ $(1 \le p_i \le n)$，其中 $p_i$ 表示从城市 $i$ 到城市 $1$ 路径上的下一个城市。

接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$ $(1 \le l_i \le r_i < 10^{9}+7)$，定义第 $i$ 号加油站的允许价格范围。

接下来的一行包含一个整数 $m$ $(1 \le m \le 200000)$，表示国王有孩子出生的年数。

接下来的 $m$ 行，每行包含四个整数 $a_i, b_i, c_i, d_i$ $(1 \le a_i, b_i, c_i, d_i \le n)$，定义第 $i$ 年出生的国王孩子将检查的两个路径。保证从城市 $a_i$ 到 $b_i$ 的路径长度等于从城市 $c_i$ 到 $d_i$ 的路径长度。

输出格式

输出 $m$ 行，每行一个数字。第 $i$ 行的数字应等于在所有城市设定汽油价格的方式数量，使得第 $i$ 年及之前出生的国王孩子在检查时未发现违规。答案请对 $10^{9} + 7$ 取模。

样例 1

输入

5
1 1 2 2
2 4
1 3
1 3
2 4
4 4
4
1 1 2 2
1 2 2 1
3 4 4 3
3 4 3 5

输出

18
18
4
0

以第一个样例为例：

在第一对儿子出生后，城市 $1$ 和 $2$ 的价格必须相等。共有 $2$ 种方式为城市 $1$ 和 $2$ 选择相同的汽油价格，使其在各自的允许范围内。因此，设定汽油价格的总方式数为 $2 \cdot 3 \cdot 3 \cdot 1 = 18$。

第二对儿子将检查路径 $1 - 2$ 和 $2 - 1$。这意味着城市 $1$ 和 $2$ 的汽油价格必须一致，而这一条件已经满足。因此，在第二对儿子出生后，答案没有变化。

第三对儿子将检查路径 $3 - 1 - 2 - 4$ 和 $4 - 2 - 1 - 3$。这意味着城市 $3$ 的汽油价格必须与城市 $4$ 的价格相等，且城市 $1$ 的价格必须与城市 $2$ 的价格相等。城市 $1$ 和 $2$ 的价格已经是相同的。对于城市 $3$ 和 $4$，有 $2$ 种方式选择相同的汽油价格，使其在各自的允许范围内。因此，设定汽油价格的总方式数为 $2 \cdot 2 \cdot 1 = 6$。

第四对儿子将检查路径 $3 - 1 - 2 - 4$ 和 $3 - 1 - 2 - 5$。这意味着城市 $4$ 和 $5$ 的价格必须相等，并且由于城市 $3$ 和 $4$ 的价格已经一致，城市 $3$、$4$ 和 $5$ 的汽油价格必须相同。城市 $3$ 的汽油价格必须不大于 $3$，而城市 $5$ 的汽油价格必须不小于 $4$。因此，在第四对儿子出生后，不存在任何方式可以设定汽油价格，使得所有检查条件满足且价格在允许范围内。

样例 2

输入

8
1 2 3 4 5 8 6
3 7
2 6
3 8
5 10
5 8
2 9
3 8
6 8
4
1 3 7 6
4 1 5 7
1 7 7 1
1 8 2 7

输出

720
120
120
1

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。