eolymp
Змагання

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}
Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB
Вхідні дані #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
Вихідні дані #1
-1
1
2
5
-1
3
4
-1
Вхідні дані #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
Вихідні дані #2
5
-1
4
4
1
Вхідні дані #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
Вихідні дані #3
2
-1
4
2
2
Автор Matvey Aslandukov