Задачи
Дерево
Дерево
Задано взвешенное дерево. Найдите кратчайшее расстояние между заданными вершинами.
Входные данные
Первая строка содержит количество вершин в дереве n~(1 \le n \le 150000). Вершины нумеруются целыми числами от 0 до n - 1. В следующих n - 1 строках содержатся три целых числа u, v, w, которые соответствуют ребру весом w~(0 \le w \le 1000), соединяющему вершины u и v. В следующей строке содержится целое число m~(1 \le m \le 75000) — количество запросов. В каждой из следующих m строк содержится по два числа — номера вершин, расстояние между которыми необходимо вычислить.
Выходные данные
Для каждого запроса выведите в отдельной строке одно число — искомое расстояние.
Пример
Входные данные #1
3 1 0 1 2 0 1 3 0 1 0 2 1 2
Выходные данные #1
1 1 2