| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 148 | 66 | 55 | 51.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$번 노드의 부모 노드의 번호를 의미한다.
포탈을 적절히 설치했을 때 발사 지점의 최대 개수를 출력한다.
6 1 1 2 3 3
2
$2$번 노드와 $5$번 노드에 포탈이 설치 되었을 때, 절반을 칠하기 위해 쏠 수 있는 노드는 $2$번 노드와 $5$번 노드로 $2$개다.
이 밖에도 발사 지점이 $2$개가 되도록 포탈을 설치하는 방법의 수는 더 있지만, $3$개 이상인 경우는 존재하지 않는다.
Contest > BOJ User Contest > Semi-Game Cup > Semi-Game Cup 4 : Grand Final D번