시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 (추가 시간 없음) | 512 MB | 0 | 0 | 0 | 0.000% |
Город Байтсбург состоит из исторической части и новой части. Историческая часть Байтсбурга представляет собой дерево из $n$ площадей, соединённых $n-1$ проспектами. Площади занумерованы последовательными целыми числами от 1 до $n$. Главная площадь города --- вершина $1$ --- является корнем дерева.
Изначально город состоял только из исторической части. Каждый год город развивается следующим образом. Пусть в начале года в городе $m$ площадей.
Вам дана конфигурация исторической части города и данные о его развитии в течение $y$ лет. Ваша задача --- отвечать на запросы вида <<найти кратчайшее расстояние между двумя площадями>>.
Первая строка входных данных содержит три целых числа $n$, $y$ и $q$ --- число площадей в исторической части, число лет, в течение которых застраивалась новая часть, и число запросов соответственно ($1 \le n,y,q \le 10^5$).
Каждая из последующих $n-1$ строк содержит по два целых числа $a$ и $b$ --- номера двух площадей в исторической части, соединённых очередным проспектом ($1 \le a,b \le n$; $a \ne b$). Гарантируется, что конфигурация проспектов и площадей является деревом. Главная площадь, которая является корнем дерева, имеет номер 1.
Каждая из последующих $y$ строк содержит по два целых числа $f$ и $t$ --- номер исходной площади в исторической части и номер площади, к которой присоединяется копия ($1 \le f \le n$; $t \ge 1$, $t$ не превосходит числа площадей на начало соответствующего года).
Каждая из последующих $q$ строк содержит по два целых числа $i$ и $j$ --- номера площадей, расстояние между которыми требуется найти. Пусть $M$ --- общее число площадей по прошествии $y$ лет застройки новой части, тогда $1 \le i,j \le M$.
Для каждого запроса выведите одно целое число --- кратчайшее расстояние между соответствующими площадями.
5 2 4 1 3 1 4 3 2 3 5 3 4 4 2 5 9 1 8 6 3 4 7
3 3 4 1