Company Planning Batch
Time limit | Memory limit | # of submissions | # of submitted users | Solved # | Accepted user ratio |
---|---|---|---|---|---|
1000 ms | 64 MiB | 24 | 9 | 8 | 88.89% |
한 회사에 $1$ 이상 $N$ 이하의 자연수 번호가 붙은 $N$명의 직원이 있습니다. 사장에게는 1번이 붙여졌습니다. 사장을 제외한 각 직원에게는 정확히 한 명의 상급자가 있습니다. 사장을 제외한 각 직원 $x$에 대해, 그(또는 그녀)의 상급자에게 붙여진 번호를 $y$로 두면 $1 \le y < x$를 만족합니다. $x$번 직원은 이 때 $y$번 직원의 하급자라고 불립니다. 이 관계는 이행성이 성립하지 않아서, $x$번 직원은 $y$번 직원의 상급자의 하급자는 아닙니다. 각 직원에게는 0명 이상의 하급자가 있을 수 있습니다.
이 회사는 "Company Planning"이라고 불리는 회사 혁신 전략을 수립하였고, 이제 실행에 착수해야 합니다. 이 프로그램에서 각 직원은 $K$명 이상의 하급자를 가질 수 없습니다. 만약 한 직원이 $K$명보다 많은 하급자를 가지고 있다면, 그(또는 그녀)는 자신의 하급자 중 일부를 해고해야만 합니다. 더욱이, 만약 어떤 직원이 해고된다면, 모든 그(또는 그녀)의 하급자들 역시 해고될 것입니다. 이 규칙은 재귀적으로 적용됩니다: 모든 그(또는 그녀)의 하급자들의 하급자들 역시 해고될 것이고, 이는 계속적으로 진행됩니다.
회사는 가능한 한 많은 직원들을 남겨두기를 원합니다. 그 이유 때문에, 회사는 적어도 $M$명의 직원을 가질 수 있도록 하는 가장 작은 $K$의 값을 알고자 합니다.
입력 형식
첫 번째 줄에 두 개의 정수 $N$과 $M$이 주어집니다. 이후 $N-1$개 줄이 주어지는데, 이 중 $i$번째 줄에는 $(i+1)$번 직원의 상급자의 번호가 주어집니다.
출력 형식
위에서 기술한 조건을 만족하는 가능한 한 작은 $K$의 값을 출력합니다.
예제
입력
7 5
1
1
1
3
3
4
출력
2
예제 설명
아래 그림은 예제 입력을 나타낸 것입니다.
4번 직원을 해고함으로서 이 회사에는 5명의 직원이 남게 됩니다. 각 직원들은 2명보다 많은 하급자를 가지고 있지 않습니다.
서브태스크
서브태스크 1 (12점)
- $1 \le M \le N \le 10$
서브태스크 2 (20점)
- $1 \le M \le N \le 1,000$
서브태스크 3 (18점)
- $1 \le M \le N \le 100,000$
- 각 직원은 최대 2명의 하급자를 가지고 있습니다.
서브태스크 4 (7점)
- $1 \le N \le 100,000$
- $M = N$
서브태스크 5 (43점)
- $1 \le N \le 100,000$