ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1471. Расстояние в дереве

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
Дано взвешенное дерево. Найти кратчайшее расстояние между заданными вершинами.

Исходные данные

Первая строка содержит целое число 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