eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Убить всех термитов

Убить всех термитов

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

На дереве живут термиты. Ваша задача убить их всех. Дерево является неориентированным связным графом с n вершинами и n - 1 ребрами. Чтобы убить термитов, Вам следует отравить некоторые вершины. Если термит попадает на вершину с ядом, то он немедленно умирает. Вы не знаете, где изначально находятся термиты. Но Вы знаете, что термиты каждый раз попадают в случайную соседнюю вершину. Однако если термит прошел ребро (u, v), то следующее ребро должно отличаться от (v, u) за исключением случая, когда термит попадает в лист (в этом случае термит поворачивается и возвращается назад). Вам следует отравить минимальное количество вершин так, чтобы термиты попали в отравленные вершины после конечного числа шагов.

Вхідні дані

Первая строка содержит одно целое число n (1n100000). Следующая строка содержит n - 1 целое число p[i] (2in), означающее что ребро соединяет p[i] и i.

Вихідні дані

Выведите минимальное количество отравленных вершин.

Приклад

Вхідні дані #1
1
Вихідні дані #1
1
Вхідні дані #2
2
1
Вихідні дані #2
1
Вхідні дані #3
8
1 1 2 1 2 3 2
Вихідні дані #3
2
Джерело 2019 Fall KBTU OPEN, Задача H