Заражене дерево#11724
У вас є бінарне дерево — це ациклічний зв'язний неорієнтований граф, що складається з вершин і n - 1 ребра. Кожна вершина має ступінь не більше , а коренем є вершина з номером , причому її ступінь не перевищує .
На жаль, корінь дерева заражений. Процес, описаний нижче, повторюється разів:
Хусейн може вибрати ще не заражену (і не видалену) вершину та видалити її разом з усіма інцидентними їй ребрами, або нічого не робити.
Після цього зараження поширюється на кожну вершину, з'єднану ребром з уже зараженою вершиною (усі раніше заражені вершини залишаються зараженими).
Ваша задача — допомогти Хусейну визначити, яку максимальну кількість вершин він може врятувати від зараження (зверніть увагу, що видалені вершини не вважаються врятованими).
Перший рядок містить кількість вершин дерева n~(2 \le n \le 3 \cdot 10^5).
Кожен з наступних n - 1 рядків містить два числа u_i і v_i~(1 \le u_i, v_i \le n), що позначають ребро дерева.
Гарантовано, що граф є бінарним деревом з коренем у вершині .
Виведіть одне ціле число — кількість врятованих вершин.
Приклад 1
Приклад 2