Сторожа в дереве
Отправить решение
Решать в редакторе
Сложность:
40%
Очки:
100 (частичный балл)
Ограничение по времени:
3.0s
Ограничение по памяти:
256M
Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch
Сторожа в дереве
Селения образуют дерево из n вершин. Сторож, поставленный в селение, охраняет его и все соседние селения. Какое наименьшее число сторожей нужно, чтобы охранялись все селения?
Ввод. В первой строке n (1 ≤ n ≤ 10^5), далее n−1 строк с рёбрами a, b.
Вывод. Наименьшее число сторожей.
Пример
Ввод:
5
1 2
1 3
2 4
2 5
Вывод:
2
Комментарии