Ветки арчи


Отправить решение Решать в редакторе

Сложность: 90%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

На склоне у села Арсланбоб растут кусты арчи. Мальчики Эмир и Нурсултан играют: по очереди отрезают одну ветку, начинает Эмир. Вместе с веткой падает и всё, что после этого отрезания больше не связано с землёй. Кто не может сделать ход (на склоне ничего не осталось), тот проиграл.

Опишем кусты деревом. Земля — вершина 0, развилки и кончики веток — вершины от 1 до n. У каждой вершины v есть родитель p[v] (0 ≤ p[v] < v); ветка — это отрезок между v и p[v]. Отрезав ветку v, игрок удаляет её вместе со всем поддеревом вершины v.

Рисунок

Найдите, сколько у Эмира выигрывающих первых ходов — таких, после которых Нурсултан проигрывает при любой своей игре. Если таких нет, выведите 0.

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

В первой строке — число n (1 ≤ n ≤ 2 · 10⁵). Во второй строке — n чисел p[1], …, p[n] (0 ≤ p[v] < v).

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

Выведите количество выигрывающих первых ходов.

Пример 1

Вход:

4
0 1 2 0

Выход:

1

Пояснение

В первом примере два куста: ветки 1 – 2 – 3 (стебель из трёх веток) и одна ветка 4. Чтобы выиграть, нужно оставить два одинаковых стебля: отрезать ветку 2 (останутся две ветки по одной) — единственный выигрывающий ход.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов n ≤ 12.

Подсказка

Принцип «двоеточия» (colon principle) и теорема Шпрага — Гранди: значение Гранди дерева равно XOR по детям корня величин «значение поддерева ребёнка + 1».


Комментарии

Еще нет ни одного комментария.