Дано взвешенное дерево. Найти кратчайшее расстояние между заданными вершинами.
Исходные данные
Первая строка содержит целое число n — количество вершин в дереве (1 ≤ n ≤ 50000).
Вершины нумеруются целыми числами от 0 до n – 1.
В следующих n – 1 строках содержится по три целых числа u, v, w, которые соответствуют ребру весом w (0 ≤ w ≤ 1000), соединяющему вершины u и v.
В следующей строке содержится целое число m — количество запросов (1 ≤ m ≤ 75000).
В следующих m строках содержится по два числа — номера вершин, расстояние между которыми необходимо вычислить.
Результат
Для каждого запроса выведите на отдельной строке одно число — искомое расстояние.
Пример
исходные данные | результат |
---|
3
1 0 1
2 0 1
3
0 1
0 2
1 2
| 1
1
2
|
Автор задачи: Дмитрий Жуков
Источник задачи: Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006