e-olymp
Соревнования

Least Common Ancestor

Колония муравьев

Группа муравьев действительно гордится тем, что они построили великолепную и большую колонию. Однако ее огромный размер стал проблемой, потому что многие муравьи не знают пути между некоторыми частями колонии. Они отчаянно нуждаются в вашей помощи!

Колония муравьев была сделана как серия из n муравейников, соединенных туннелями. Муравьи, будучи предусмотрительными, в процессе постройки последовательно нумеровали муравейники. Первый муравейник, имеющий номер 0, не нуждался ни в каком туннеле, но для каждого последующего муравейника, с 1 по n1, муравьи также построили один туннель, соединяющий новый муравейник с одним из существующих муравейников. Конечно, этого туннеля было достаточно, чтобы любой муравей мог отправиться в любой ранее построенный муравейник, возможно, пройдя через другие муравейники на своем пути. Поэтому они не беспокоились о создании дополнительных туннелей и продолжали строить больше муравейников.

Ваша задача - учитывая структуру колонии и набор запросов, вычислить для каждого запроса кратчайший путь между парами муравейников. Длина пути - это сумма длин всех туннелей, которые необходимо преодолеть.

Входные данные

Каждый тест состоит из нескольких строк. Первая строка содержит количество муравейников n (2n105) в колонии. Каждая из следующих n1 строк содержит два числа, описывающих туннель. Строка i (1in1) содержит Ai и Li, указывающих на то что муравейник i напрямую соединен с муравейником Ai туннелем длины Li (0Aii1 и 1Li109). Следующая строка содержит количество запросов q (1q105). Каждая из следующих q строк описывает запрос и содержит два разных числа s и t (0s, tn1) - номера муравейников, между которыми следует найти расстояние.

За последним тестом находится строка из одного нуля.

Выходные данные

Для каждого теста выведите одну строку с q целыми числами, каждая из которых является длиной кратчайшего пути между парой муравейников запроса. Запишите результаты для каждого запроса в том же порядке, в котором запросы были заданы во входных данных.

Лимит времени 1 секунды
Лимит использования памяти 128 MiB
Входные данные #1
6
0 8
1 7
1 9
0 3
4 2
4
2 3
5 2
1 4
0 3
2
0 1
2
1 0
0 1
6
0 1000000000
1 1000000000
2 1000000000
3 1000000000
4 1000000000
1
5 0
0
Выходные данные #1
16 20 11 17
1 1
5000000000
Источник 2010 ACM South America, Latin America, Октябрь 22, Задача A