eolymp
Задачи

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

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

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

Входные данные

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

Выходные данные

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #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