Задача №112120. Прогулка (AB)
Устав от постоянных войн, Бамблби решил прокатиться по своему городу и посмотреть достопримечательности. В его навигационной системе город представлен в виде связанного графа, содержащего ровно n вершин и n - 1 ребро. Каждой вершине графа соответствует некоторая площадь в городе. Между некоторыми площадями существуют двусторонние дороги — ребра в графе. Известно, что от любой площади города можно добраться до любой другой, проехав при этом только по дорогам.
Про каждую дорогу известно, какое время Бамблби тратит на проезд по ней. Бамблби хочет потратить на прогулку ровно T единиц времени. Кроме этого, он хочет объехать ровно K+1 различных площадей, побывав на каждой не более одного раза. Помогите ему выбрать 2 соответствующие площадям вершины так, чтобы путь между ними состоял ровно из K различных дорог, а время, затраченное на поездку, было бы равно T .
Бамблби тратит время только на перемещения по дорогам, суммарное время его присутствия на площадях равно нулю.
В первой строке входного файла задано три числа n , T и K ( 1 ≤ n ≤ 100 000 , 0 ≤ K ≤ 100 000 , 0 ≤ T ≤ 1 000 000 000 ) — количество площадей, необходимое время поездки и необходимое количество дорог, участвующих в поездке.
Следующие n - 1 строк содержат по три числа a i , b i и t i ( 1 ≤ a i , b i ≤ n , 1 ≤ t i ≤ 10000 ) — описание очередной дороги. Первые два числа являются номерами площадей, соединенных этой дорогой, а третье — временем поездки по ней.
Выведите ответ на задачу. Если таких вершин не существует, выведите 00 . Числа ответа необходимо упорядочить по возрастанию.
В случае, если вариантов ответа несколько, выведите лексикографически минимальную пару.
Первая группа тестов состоит из тестов, для которых выполняется ограничение n ≤ 100 . Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 20 баллов.
Вторая группа тестов состоит из тестов, для которых выполняется ограничение n ≤ 1000 . Баллы за эту группу начисляются только при прохождении всех тестов группы. Стоимость группы составляет 20 баллов.
Третья группа тестов состоит из тестов, для которых выполняется ограничение n ≤ 100000 . Тесты в этой группе оцениваются независимо. Стоимость группы составляет 60 баллов.
5 3 2 1 2 1 2 3 1 3 5 1 2 4 2
1 4
2 0 0 1 2 10
1 1
2 1 0 1 2 10
0 0