Найдите центр дерева
Вам даны
n городов, соединённых между собой n-1 дорогами. Все города связаны друг с другом (возможно, через промежуточные города). Вам необходимо выбрать место для столицы таким образом, чтобы оно было максимально выгодным.По вашему решению, лучшим местоположением считается то, где максимально возможное расстояние до городов на границе (которые соединены только с одним другим городом) будет минимальным. Какие города будут лучшими кандидатами на роль столицы?
Входные данные
В первой строке входных данных задано целое число
v (1 ≤ v ≤ 100000).В следующих
v-1 строках содержатся пары целых чисел v1, v2 (1 ≤ v1, v2 ≤ v), означающие, что вершина v1 соединена с вершиной v2 и наоборот.Выходные данные
Программа должна вывести лучшие варианты для размещения столицы в порядке возрастания.
Примеры
Входные данные | Выходные данные |
4
1 2
2 3
3 4 | 2 3 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB