Нахождение центроида (centroid) дерева
Вам дано дерево с
v вершинами. Ваша задача — найти центроид дерева. Центроидом называется такая вершина, что при её удалении все оставшиеся поддеревья имеют размер не более вершин.Ввод
Первая строка входных данных содержит одно целое число
v (1 ≤ v ≤ 100 000).Последующие
v-1 строк содержат пары целых чисел v1, v2 (1 ≤ v1, v2 ≤ v), указывающие, что вершина v1 соединена с вершиной v2 и наоборот.Вывод
Программа должна вывести центроид данного дерева. Если существует несколько подходящих ответов, можно вывести любой из них.
Примеры
Ввод | Вывод |
3
1 2
1 3 | 1 |
5
1 2
2 3
3 4
3 5 | 3 |
Подсказка
Вы можете вычислить размер поддерева (количество дочерних вершин) для каждой вершины.
Затем, для каждой вершины проверьте, что размеры всех её поддеревьев не превышают половину от общего числа вершин в дереве. При этом учитывайте как дочерние узлы, так и часть дерева «снаружи», то есть
v-currentNodeSize, которая относится к родительскому поддереву.Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB