Задача №111233. Белочка (Б)
Гуляя по лесу, Настя встретила белочку и решила устроить ей настоящее испытание. Однако, всё осложнилось тем, что белочка ещё маленькая и не умеет прыгать по воздуху между ветками — она может ходить только по соседним веткам.
Точками на дубе назовём концы веток и разветвления (места, где одна ветка разветвляется на несколько других).
Настя выбрала один из многих дубов в лесу и решила выбрать две точки на дубе, на одну из которых она решила повесить орешек, а на другую — посадить белочку. Настя хочет выбрать точки таким образом, чтобы белочке нужно было пройти как можно большее расстояние до орешка.
К сожалению, Настя не может самостоятельно справиться с этой задачей. Помогите ей в этом.
В первой строке введено целое число N — количество точек на дубе.
В следующих N - 1 строках описываются ветки дуба. Каждая ветка характеризуется тремя целыми числами: Ai, Bi, Li(1 ≤ Ai, Bi ≤ N;1 ≤ Li ≤ 104), разделёнными пробелом, где Ai, Bi — номера точек на дубе, соединяемых веткой i, а Li — длина ветки i.
Гарантируется, что существует путь по веткам между любыми двумя точками на дубе.
Выведите три целых числа через пробел: максимальную длину возможного пути белочки до орешка, номер точки, на которую нужно посадить белочку, и номер точки, на которую нужно повесить орешек.
Если возможных ответов несколько, выведите любой из них.
3
1 2 1
1 3 1
2 2 3
Тесты в этой задаче состоят из четырёх групп:
- 0. Тест 1. Тест из условия. Оценивается в 0 баллов.
- 1. Тесты 2 - 18. Тесты с ограничением 2 ≤ N ≤ 100. Группа тестов оценивается в 40 баллов, при этом баллы ставятся только за прохождение всех тестов группы.
- 2. Тесты 19 - 31. Тесты с ограничением 2 ≤ N ≤ 5000. Группа тестов оценивается в 30 баллов, при этом баллы ставятся только за прохождение всех тестов 1 и 2 группы.
- 3. Тесты 32 - 50. Тесты с ограничением 2 ≤ N ≤ 105. Группа тестов оценивается в 30 баллов, при этом баллы ставятся только за прохождение всех тестов 1, 2 и 3 группы.