Группа муравьев действительно гордится тем, что они построили великолепную и большую колонию. Однако ее огромный размер стал проблемой, потому что многие муравьи не знают пути между некоторыми частями колонии. Они отчаянно нуждаются в вашей помощи!
Колония муравьев была сделана как серия из n муравейников, соединенных туннелями. Муравьи, будучи предусмотрительными, в процессе постройки последовательно нумеровали муравейники. Первый муравейник, имеющий номер 0, не нуждался ни в каком туннеле, но для каждого последующего муравейника, с 1 по n − 1, муравьи также построили один туннель, соединяющий новый муравейник с одним из существующих муравейников. Конечно, этого туннеля было достаточно, чтобы любой муравей мог отправиться в любой ранее построенный муравейник, возможно, пройдя через другие муравейники на своем пути. Поэтому они не беспокоились о создании дополнительных туннелей и продолжали строить больше муравейников.
Ваша задача - учитывая структуру колонии и набор запросов, вычислить для каждого запроса кратчайший путь между парами муравейников. Длина пути - это сумма длин всех туннелей, которые необходимо преодолеть.
Каждый тест состоит из нескольких строк. Первая строка содержит количество муравейников n (2 ≤ n ≤ 10^5
) в колонии. Каждая из следующих n − 1 строк содержит два числа, описывающих туннель. Строка i (1 ≤ i ≤ n − 1) содержит A[i]
и L[i]
, указывающих на то что муравейник i напрямую соединен с муравейником A[i]
туннелем длины L[i]
(0 ≤ A[i]
≤ i − 1 и 1 ≤ L[i]
≤ 10^9
). Следующая строка содержит количество запросов q (1 ≤ q ≤ 10^5
). Каждая из следующих q строк описывает запрос и содержит два разных числа s и t (0 ≤ s, t ≤ n − 1) - номера муравейников, между которыми следует найти расстояние.
За последним тестом находится строка из одного нуля.
Для каждого теста выведите одну строку с q целыми числами, каждая из которых является длиной кратчайшего пути между парой муравейников запроса. Запишите результаты для каждого запроса в том же порядке, в котором запросы были заданы во входных данных.