e-olymp
favorite Нам необходимо немного Вашей помощи чтобы сайт продолжал работать, нажмите на банер чтобы узнать больше.
Задачи

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

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

На дереве живут термиты. Ваша задача убить их всех. Дерево является неориентированным связным графом с 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