- Описание
- Отправленные решения
401. Два центра
Дано взвешенное дерево $T$. Назовем 2-радиусом минимальную величину $r$, для которой существуют 2 смежные вершины $u$ и $v$, что для любой вершины $w$ верно неравенство:
$min(distance(u, w), distance(v, w)) \le r$Формат ввода
В первой строке записано единственное число $n$ $-$ количество вершин в дереве ($3 \le n \le 2222$).
Далее в $n-1$ строке идут описания ребер в формате $a$, $b$, $c$ ($1 \le a < b \le n$, $1 \le c \le 500\ 000$) $-$ между вершинами $a$ и $b$ есть ребро длины $c$.
Формат вывода
В единственной строке выведите значение 2-радиуса.
Ограничения
Ограничение времени
2 с
Ограничение памяти
256 МБ
Пример 1
Ввод
3
1 2 5
2 3 10
Вывод
5
Пример 2
Ввод
5
1 2 1
1 3 1
1 4 1
1 5 1
Вывод
1
Пример 3
Ввод
10
1 2 16
2 3 18
1 4 49
1 5 29
5 6 20
3 7 29
6 8 34
7 9 9
9 10 32
Вывод
88