e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Соревнования

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