Ветки арчи
На склоне у села Арсланбоб растут кусты арчи. Мальчики Эмир и Нурсултан играют: по очереди отрезают одну ветку, начинает Эмир. Вместе с веткой падает и всё, что после этого отрезания больше не связано с землёй. Кто не может сделать ход (на склоне ничего не осталось), тот проиграл.
Опишем кусты деревом. Земля — вершина 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».
Комментарии