Задача №115251. Цены на бензин
Берляндия — это огромная страна, состоящая из \(n\) городов. Дорожную сеть Берляндии можно представить в виде корневого дерева, то есть всего в стране \(n - 1\) дорога, и от любого города можно добраться до любого другого ровно по одному пути, если не посещать никакой город дважды. Для удобства представления страны, для каждого города \(i\) зафиксирован город \(p_i\), равный первому городу, в который надо ехать из города \(i\), чтобы добраться до города \(1\). Иными словами, город \(p_i\) равен предку города \(i\), если дерево подвесить за город \(1\).
В каждом городе Берляндии работает по одной заправке. У заправок особое ценообразование, и для каждой заправки зафиксирован диапазон цен, за которые там готовы продавать бензин. Заправка в городе с номером \(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\) лет. Другими словами, для каждого \(i\) от \(1\) до \(m\) посчитайте, сколькими способами можно выставить цены на бензин во всех заправках, чтобы после рождения первых \(i\) пар детей короля, все их проверки не выявили нарушений, а на любой заправке цена находилась в допустимом диапазоне цен. Так как число таких способов может быть большим, посчитайте ответ по модулю \(10^9 + 7\).
В первой строке дано единственное целое число \(n\) (\(1 \le n \le 200\,000\)) — число городов в Берляндии.
Во второй строке даны \((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\) и \(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. Значит, после рождения четвёртой пары сыновей не существует способов выставить цены на бензин так, чтобы все проверки выполнялись и цены находились в необходимых диапазонах.
Тесты к этой задаче состоят из 8 групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов некоторых из предыдущих групп. Обратите внимание, прохождение тестов из условия не требуется для некоторых групп. Offline-проверка означает, что результаты тестирования вашего решения на данной группе станут доступны только после окончания соревнования.
| Доп. ограничения | |||||
| Группа | Баллы | \(n\) | \(m\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 12 | \(n \le 300\) | \(m \le 300\) | 0 | |
| 2 | 10 | \(n \le 3000\) | \(m \le 3000\) | – | \(p_i = i - 1\) |
| 3 | 9 | \(n \le 3000\) | \(m \le 3000\) | 0, 1, 2 | |
| 4 | 16 | – | – | 0 – 3 | Cуммарная длина всех путей, на которых будет проходить проверка цен, не превосходит \(10^8\) |
| 5 | 10 | \(n \le 100\,000\) | \(m \le 100\,000\) | 2 | \(p_i = i - 1\) |
| 6 | 12 | – | – | 2, 5 | \(p_i = i - 1\) |
| 7 | 13 | \(n \le 100\,000\) | \(m \le 100\,000\) | 0 – 3, 5 | |
| 8 | 18 | – | – | 0 – 7 | Offline-проверка. |
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