숨은 상사

일부가 비어 있는 부모 배열이 주어질 때, 빠진 감독자를 채워 루트 있는 트리를 완성하고 서로 겹치지 않는 부모-자식 짝의 최대 개수를 구한다.

어려움8트리동적 계획법그리디DFS아직 제출이 없습니다시간 제한3초메모리 제한512 MB

문제

헬레나는 큰 회사에서 심리학자로 일한다. 이번에 맡은 일은 직원 사이의 관계를 좋게 만드는 팀 빌딩 게임을 준비하는 것이다. 사장을 뺀 모든 직원에게는 상사가 정확히 한 명 있다. 그래서 직원 전체는 트리를 이룬다. 각 직원이 정점이고, 어떤 정점의 부모는 그 직원의 상사다. 트리의 루트는 사장이며 사장의 번호는 11이다.

이 게임의 팀은 두 사람으로 이루어지고, 한 팀은 어떤 직원과 그 직원의 상사로 구성한다. 한 사람은 많아야 한 팀에만 들어간다.

헬레나는 사장을 뺀 모든 직원에게 상사의 번호를 알려 달라고 했지만 일부는 답하지 않았다. 헬레나는 답하지 않은 직원마다 가짜 상사를 한 명씩 정해 주려고 한다. 물론 진짜 상사와 가짜 상사를 합친 관계도 사장을 루트로 하는 트리여야 한다.

가짜 상사를 가장 잘 정했을 때 만들 수 있는 팀의 최대 개수를 구하라.

입력

첫째 줄에 직원 수 nn이 주어진다 (2n1000002 \le n \le 100\,000).

둘째 줄에 n1n - 1개의 정수 p2,p3,,pnp_2, p_3, \dots, p_n이 주어진다 (0pin0 \le p_i \le n). pip_i는 직원 ii가 알려 준 상사의 번호이고, 답하지 않은 직원은 pip_i00이다. 사장의 번호는 11이다.

답하지 않은 직원 모두에게 가짜 상사를 정해서 전체 직원이 사장을 루트로 하는 트리를 이루게 하는 방법이 적어도 하나 있다.

출력

만들 수 있는 팀의 최대 개수를 한 줄에 출력한다. 상사 배정 자체는 출력하지 않는다.