eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Дерево

Дерево

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Задано взвешенное дерево. Найдите кратчайшее расстояние между заданными вершинами.

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

Первая строка содержит количество вершин в дереве 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
Автор Дмитрий Жуков
Источник 2006 Petrozavodsk Summer Session, Ural SU and Orel STU Contest, August