题目背景

CF1801E

题目描述

伯利兰是一个由 $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$ 出发。第一个孩子沿着从 $a_i$ 到 $b_i$ 的路径前进，第二个孩子则沿着从 $c_i$ 到 $d_i$ 的路径前进。他们会依次检查：起点 $a_i$ 和 $c_i$ 的油价是否相同，然后检查路径上的第二个城市是否油价相同，依此类推，直到终点 $b_i$ 和 $d_i$ 的油价也要一致。保证从 $a_i$ 到 $b_i$ 的路径长度和从 $c_i$ 到 $d_i$ 的路径长度相同。

所有加油站都必须严格遵守法律，因此所有的油价检查都不能出现违规。请你帮助伯利兰的加油站计算，在 $m$ 年内，他们有多少种合法的油价设置方式。换句话说，对于每个 $i$ 从 $1$ 到 $m$，请计算在前 $i$ 年出生的所有王子进行检查后，所有检查都不出现违规，且每个加油站的油价在允许区间内的情况下，总共有多少种油价分配方案。由于答案可能很大，请对 $10^9 + 7$ 取模输出。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 200\,000$），表示伯利兰的城市数量。

第二行包含 $n-1$ 个整数 $p_2,\ p_3,\ \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 200\,000$），表示国王有多少年每年出生两位儿子。

接下来的 $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$ 取模。

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

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

提示

样例解释

以第一个样例为例：

• 在头两位王子出生后，城市 $1$ 和城市 $2$ 的油价必须相同。可以在允许的区间内为城市 $1$ 和 $2$ 选择相同的油价方式有 $2$ 种。剩下城市 $3$ 和 $4$ 的油价分别有 $3$ 种和 $3$ 种选择。总方案数为 $2 \times 3 \times 3 \times 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 \times 2 \times 1 = 6$。
• 第四对王子检查的是 $3-1-2-4$ 和 $3-1-2-5$，这要求城市 $4$ 和 $5$ 的油价一致，而城市 $3$ 和 $4$ 已经一致，因此 $3$、$4$、$5$ 三个城市的油价都要一致。城市 $3$ 的油价不能超过 $3$，城市 $5$ 的油价不能低于 $4$，因此不存在满足条件的方案，答案为 $0$。

评分说明

本题的数据分为 8 组。只有通过某一组全部测试点，且通过部分之前组全部测试点，才能获得该组分数。有些分组不要求通过样例测试点。“离线评测”表示该组的测试结果只会在比赛结束后公布。

组别	分值	$n$	$m$	必须通过的组	备注
0		--			样例测试点
1	12	$n \le 300$	$m \le 300$	0
2	10	$n \le 3000$	$m \le 3000$	--	$p_i = i - 1$
3	9			0, 1, 2
4	16	--		0 -- 3	所有检查路径的总长度不超过 $10^8$
5	10	$n \le 100\,000$	$m \le 100\,000$	2	$p_i = i - 1$
6	12	--		2, 5
7	13	$n \le 100\,000$	$m \le 100\,000$	0 -- 3, 5
8	18	--		0 -- 7	离线评测