e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Competitions

Ukrainian Olympiad in Informatics, IV Stage, I Round

Бандиты на дереве

Существует $n$ городов, пронумерованных от $1$ до $n$. Все города соединены с помощью $(n - 1)$ дорог так, что от каждого города можно добраться до каждого. Каждая дорога имеет определенную длину. Известно, что город с номером $i$ был захвачен кланом бандитов с номером $a_i$ ($1 \leq a_i \leq n$) в момент времени $t_i$. После захвата города $i$ (то есть, начиная с момента времени $t_i$ \textbf{включительно}), через него могут проходить только представители клана $a_i$. Ответьте на $m$ вопросов следующего вида: \begin{itemize} \item \t{u v b T} --- сможет ли представитель клана $b$ попасть из города $u$ в город $v$, если он начнет свое путешествие в момент времени $T$. В случае невозможности совершения путешествия, необходимо также сообщить номер первого города на пути от $u$ до $v$, через который невозможно проехать. \end{itemize} \InputFile Первая строка содержит целое число $n$ ($2 \leq n \leq 10^5$) --- количество городов. Каждая из следующих $(n - 1)$ строк содержит два целых числа $p_i$ и $d_i$ ($1 \leq p_i < i$, $1 \leq d_i \leq 10^3$), обозначающие дорогу между городами $i$ и $p_i$ длины $d_i$. Индексация начинается с $2$. Следующая строка содержит $n$ целых чисел $a_i$ ($1 \leq a_i \leq n$), обозначающих номера кланов, захвативших соответствующий город. Следующая строка содержит $n$ целых чисел $t_i$ ($1 \leq t_i \leq 10^9$), обозначающих моменты времени захвата каждого города. Следующая строка содержит целое число $m$ ($1 \leq m \leq 10^5$) --- количество запросов. Последние $m$ строк описывают запросы. Каждый из них содержит четыре целые числа $u_i$, $v_i$, $b_i$, $T_i$ ($1 \leq u_i, v_i, b_i \leq n$, $1 \leq T_i \leq 10^9$) --- номера начального и конечного городов очередного пути, номер клана путешественника, и момент времени начала путешествия соответственно. \OutputFile Для каждого запроса выведите в отдельной строке одно целое число --- номер первого города на пути от $u$ до $v$, через который невозможно пройти. Если такого города не существует, выведите <<\t{-1}>>. Обратите внимание на большой объем входных и выходных данных в этой задаче. Советуем использовать быстрые средства ввода и вывода, например \t{scanf/printf} вместо \t{cin/cout} в языке \t{C ++} и \t{sys.stdin.readline} вместо \t{input} в \t{Python}. Также советуем использовать интерпретатор \t{PyPy} при решении задачи на \t{Python}. \Scoring \begin{enumerate} \item ($7$ баллов): $p_i = 1$; \item ($9$ баллов): $n, m \leq 10^3$; \item ($11$ баллов): $p_i = i - 1, t_i = 1$; \item ($18$ баллов): $p_i = i - 1, a_i = 1, b_i = 2$; \item ($15$ баллов): $p_i = i - 1$; \item ($11$ баллов): $t_i = 1$; \item ($17$ баллов): $a_i = 1, b_i = 2$; \item ($12$ баллов): без дополнительных ограничений. \end{enumerate}
Time limit 1 second
Memory limit 256 MiB
Input example #1
5
1 7
1 3
2 2
2 1
1 1 2 3 3
10 4 15 15 1
8
5 3 3 1
5 3 3 2
5 3 3 3
5 3 1 1
4 3 1 2
4 3 1 3
3 4 1 3
2 1 1 100
Output example #1
-1
1
2
5
-1
3
4
-1
Input example #2
5
1 4
1 1
1 1
1 4
3 2 2 2 2
4 4 6 7 5
5
5 2 4 7
1 1 1 3
4 2 1 9
1 4 3 7
3 4 2 4
Output example #2
5
-1
4
4
1
Input example #3
5
1 4
2 1
3 3
4 1
2 1 2 3 2
8 3 7 7 9
5
1 5 2 4
1 2 1 4
5 2 1 6
1 4 3 5
1 5 4 7
Output example #3
2
-1
4
2
2
Author Matvey Aslandukov
Source 2021 Ukrainian Olympiad in Informatics, Stage IV, Round I