부분트리 활성화

새해 축하를 위해 버시와 친구들은 빛나는 장식이 많이 달린 큰 트리를 만들었다. 버시는 리모컨으로 장식을 켜고 끌 수 있다. 해가 뜨기 전에 버시는 장식 몇 개를 어떤 순서로 토글하려 한다(같은 장식을 여러 번 토글해도 된다). 트리는 처음과 끝에 장식이 모두 꺼져 있어야 한다. 켜진 장식의 집합이 어떤 정점을 루트로 하는 부분트리와 정확히 같으면 트리가 멋있어 보인다고 버시는 생각한다. 토글 순서는 모든 부분트리에 대해, 켜진 장식 전체가 그 부분트리와 정확히 같아지는 순간이 적어도 한 번 있도록 해야 한다. 장식을 켜고 끄는 데는 에너지가 드니, 버시는 토글 횟수를 가능한 한 적게 하려 한다.

형식적으로 말하면, 정점에 $1$부터 $N$까지 번호가 붙은 트리가 있고 루트는 $1$이다 ($2 \le N \le 2 \cdot 10^5$). 처음에는 모든 정점이 꺼져 있다. 연산 한 번은 정점 하나의 상태를 꺼짐에서 켜짐으로, 또는 켜짐에서 꺼짐으로 바꾼다. 정점 $r$을 루트로 하는 부분트리는 $1$에서 $v$로 가는 경로에 $r$이 포함되는 모든 정점 $v$의 집합이다(양 끝 포함). 다음 두 조건을 만족하는 연산 수열의 최소 길이를 구하라.

• $N$개의 부분트리 각각에 대해, 켜진 정점의 집합이 그 부분트리와 정확히 같은 순간이 있다.
• 연산 수열이 끝난 뒤 모든 정점이 꺼져 있다.

첫 번째 줄에 $N$이 주어진다.

두 번째 줄에는 $p_2 \dots p_N$이 주어지며, $p_i$는 정점 $i$의 부모이다 ($1 \le p_i < i$).

연산 수열의 최소 길이를 출력한다.

부분트리는 $\{1,2,3\}$, $\{2\}$, $\{3\}$ 세 개이다. 다음은 최소 길이를 갖는 연산 수열 중 하나이다.

정점 2 켜기
(켜진 정점이 2를 루트로 하는 부분트리가 된다)
정점 1 켜기
정점 3 켜기
(켜진 정점이 1을 루트로 하는 부분트리가 된다)
정점 1 끄기
정점 2 끄기
(켜진 정점이 3을 루트로 하는 부분트리가 된다)
정점 3 끄기