Для празднования Нового Года Беси и её друзья сконструировали гигантское
дерево со светящимися украшениями. Беси имеет возможность включать и выключать
украшения удалённо. Прежде чем взойдёт солнце, она хочет переключить некоторые
украшения в некотором порядке (возможно переключая украшения более одного раза),
так, чтобы дерево начиналось и заканчивалось невключёнными украшениями.
Беси считает, что дерево выглядит здорово, если множество включённых украшений
является точным поддеревом с корнем в некоторой вершине. Она хочет, чтобы порядок,
в котором она переключает украшения соответствовал свойству, что для каждого поддерева
в некоторый момент времени были включены все его украшения. Дополнительно,
она хочет найти минимальное количество переключений для решения этой задачи.
Формально, у Вас есть дерево с вершинами помеченными \(1\dots N\)
(\(2\le N\le 2\cdot 10^5\)) с корнем в вершине \(1\). Каждая вершина изначально не активна.
За одну операцию Вы можете переключить одну вершину из неактивного состояния в активное
или обратно. Выведите минимально возможную длину последовательности операций, удовлетворяющей обоим нижеуказанным условиям:
- Определим, что поддерево с корнем в вершине \(r\) состоит из всех вершин \(v\)
таких, что \(r\) лежит на пути из \(1\) в \(v\) включительно. Для каждого из \(N\)
поддеревьев дерева существует момент времени, когда множество активных вершин
сосредоточено именно в этом поддереве.
- Каждая вершина неактивна после выполнения всей последовательности операций.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит
\(N\).
Вторая строка содержит \(p_2 \dots p_N\) (\(1\le p_i<i\)), где \(p_i\) обозначает родительскую
вершину вершины \(i\) в этом дереве.
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите минимально возможную длину.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 1
|
6
|