시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB2172000.000%

문제

어떤 회사의 작업 공정은 아래에서 위로(bottom-up) 진행된다. 즉, 말단 사원들이 우선 처음 부분을 진행하고, 작업이 완료되면 그 상사가 작업물을 전달받아 다음 작업을 진행하고, 다시 그 위의 상사가 작업을 마저 진행하는 방식이다. 이러한 작업 공정을 정리하면 다음과 같다.

  1. 각각의 직원들은 사장을 제외하고는 한 명의 직속 상사를 가지고 있다.
  2. 각각의 직원은 자신의 하사(직속 하사 및 직속 하사의 하사)들이 모두 작업을 완료한 후에 작업을 시작할 수 있다. 말단 직원들의 경우에는 아무 때에나 작업을 시작할 수 있다.
  3. 작업은 사장이 작업을 완료한 후에 끝난다.
  4. 모든 작업은 시작부터 완료까지 1만큼의 시간이 걸린다고 한다.

이러한 작업 공정을 이용하여 이 회사에서는 작업을 진행하고 있었다. 하지만 경기가 나빠지면서 사장은 일부 직원을 해고하기로 결심하였다. 직원을 해고한 후의 빈 자리는 다른 직원을 이용하여 대체하기로 하였다. 즉, 말단 직원들의 경우에는 자신의 작업을 완료한 후에는 할 일이 없게 되는데, 이때 다른 상사의 작업을 이 직원들이 진행하면 좀 더 적은 수의 직원으로도 작업을 진행할 수 있다. 반대로 말단 직원들을 해고한 후에 사장 등의 상사들이 그 작업을 진행할 수도 있다. 단, 직원들을 해고한 후에도 작업의 효율이 떨어지지 않아야 한다. 즉, 모든 직원이 있었을 때 보다 전체 작업이 완료되는 시간이 늘어나서는 안 된다.

각 직원들의 관계가 주어졌을 때, 전체 작업 완료 시간을 유지하면서 해고할 수 있는 직원의 최대 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 직원의 수를 나타내는 정수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 차례로 1번, 2번, …, N번 직원의 직속 상사의 번호가 주어진다. 사장의 경우에는 -1이 주어진다.

출력

첫째 줄에 전체 직원들이 있을 때 필요한 최소 작업 완료 시간을 출력한다. 둘째 줄에 해고할 수 있는 직원의 최대 수를 출력한다.

예제 입력 1

7
-1
1
1
2
2
3
3

예제 출력 1

3
3

힌트

  • 시간 0-1: 남아있는 네 명의 직원이 동시에 4, 5, 6, 7번 직원의 작업을 수행한다.
  • 시간 1-2: 다음에 두 명의 직원이 2, 3번 직원의 작업을 수행한다.
  • 시간 2-3: 마지막으로 1번 직원의 작업을 수행한다.

출처