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

Ural SU and Orel STU contest. Petrozavodsk training camp. Summer 2006

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

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

Ограничение времени: 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
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1471. Расстояние в дереве