시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB148665551.402%

문제

페인트 토끼의 토끼굴은 $1$번 노드를 루트로 하는 $N$개의 노드로 이루어진 트리로 표현할 수 있다(단, $N$은 짝수). 각 노드는 토끼굴의 방을 의미한다. 게임에서는 꾸미는 것도 중요하기 때문에 페인트를 좋아하는 토끼는 토끼굴에서 정확히 $\frac{N}{2}$개의 방을 색칠하려고 한다. 토끼에게는 단 하나의 페인트 탄이 있으며, 특정 노드에 탄을 쏘면 다음과 같은 규칙으로 페인트가 번진다.

  • 처음 탄을 맞은 노드는 색칠된다.
  • 색칠된 노드의 모든 자식 노드는 연쇄적으로 색칠된다.

GM 77은 토끼를 돕기 위해 서로 다른 두 노드 $u$, $v$를 연결하는 포탈을 정확히 하나 설치하기로 했다. 이 때 두 노드 사이에는 페인트가 양방향으로 흐른다. 즉, $u$가 색칠되면 추가로 $v$와 그 자손들이 모두 색칠되고, 반대로 $v$가 색칠되면 추가로 $u$와 그 자손들이 모두 색칠된다.

토끼가 불쌍했던 GM 77의 목표는 포탈을 적절히 설치하여, 어느 한 노드에 페인트 탄을 쐈을 때 정확히 $N/2$개의 노드가 색칠되게 만드는 발사 지점의 개수를 최대화하는 것이다. 포탈을 최적으로 설치했을 때, 이러한 발사 지점의 최대 개수를 구하여라.

입력

첫째 줄에 노드의 수를 나타내는 정수 $N$이 들어온다.

두 번째 줄에는 $N-1$개의 정수 $P_2$, $P_3$, $\cdots$, $P_N$이 공백으로 구분되어 주어진다. $P_i$는 트리에서 $i$번 노드의 부모 노드의 번호를 의미한다.

출력

포탈을 적절히 설치했을 때 발사 지점의 최대 개수를 출력한다.

제한

  • 주어지는 모든 수는 정수이다.
  • $4\le N\le 100\, 000$, $N$은 짝수
  • $1\le P_i<i$ ($2\le i\le N$)

예제 입력 1

6
1 1 2 3 3

예제 출력 1

2

$2$번 노드와 $5$번 노드에 포탈이 설치 되었을 때, 절반을 칠하기 위해 쏠 수 있는 노드는 $2$번 노드와 $5$번 노드로 $2$개다.

이 밖에도 발사 지점이 $2$개가 되도록 포탈을 설치하는 방법의 수는 더 있지만, $3$개 이상인 경우는 존재하지 않는다.

출처

Contest > BOJ User Contest > Semi-Game Cup > Semi-Game Cup 4 : Grand Final D번