← 返回题目列表

Codeforces · 1801/E

E. 汽油价格

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

Berland每个城市都有一个加油站。加油站有特殊的定价,并且每个加油站都有一个固定的价格范围可供出售汽油。城市中编号为 $$$i$$$ 的加油站已准备好以从 $$$l_i$$$ 到 $$$r_i$$$(含)的任何价格出售汽油。

Berland 国王 - 是一位模范顾家男人,在 $$$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$$$的路径长度一致。

加油站必须严格遵守法律,因此所有汽油价格检查都不应发现违规行为。帮助 Berland 加油站找出有多少种方法可以设定 $$$m$$$ 年的汽油价格。换句话说,对于从 $$$1$$$ 到 $$$m$$$ 的每个 $$$i$$$,计算有多少种方法可以在所有加油站设定汽油价格,以便在国王的第一对 $$$i$$$ 孩子出生后,他们的所有检查都没有发现违规行为,并且在任何加油站的价格都在可接受的价格范围内。由于此类方法的数量可能很大,因此请以 $$$10^9 + 7$$$ 为模计算答案。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 200\,000$$$) — Berland 的城市数量。

第二行包含$$$(n - 1)$$$数字$$$p_2,\ p_3,\ p_4,\ \ldots,\ p_n$$$ ($$$1 \le p_i \le n$$$),其中$$$p_i$$$表示从城市$$$i$$$到城市$$$1$$$途中的下一个城市的号码。

在以下每一行中,给出两个整数 $$$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$$$ 取模的数字。

示例

输入 #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

输出 #1

18
18
4
0

输入 #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

输出 #2

720
120
120
1

注意

考虑第一个例子。

前两个儿子出生后,$$$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 = 4$$$。 第四对儿子将检查轨道 $$$3 - 1 - 2 - 4$$$ 和 $$$3 - 1 - 2 - 5$$$ 上的价格。这意味着$$$4$$$ 和$$$5$$$ 城市的价格应该相等,并且由于$$$3$$$ 和$$$4$$$ 城市的价格已经一致,因此$$$3$$$、$$$4$$$ 和$$$5$$$ 城市的汽油价格应该相同。 $$$3$$$城市的汽油价格应该不超过3,$$$5$$$城市的汽油价格应该不低于4。所以,第四对儿子出生后,没有办法设定汽油价格,以便进行所有检查并使价格在要求的范围内。