슈퍼컴퓨터

Byteasar는 새로운 구조의 슈퍼컴퓨터를 설계했다. 동일한 처리 장치를 여러 개 두며, 각 장치는 한 시간 단위에 명령 하나를 실행한다.

프로그램은 순차적이 아니라 트리 구조다. 각 명령은 0개, 1개, 또는 여러 개의 후속 명령을 가질 수 있으며, 자신이 그 부모 명령이다.

명령은 사용 가능한 모든 처리 장치에서 병렬 실행할 수 있다. 단, 부모 명령이 먼저 실행된 뒤에만 자식 명령을 실행할 수 있다. 이미 실행된 명령의 자식들은 처리 장치 수만큼 동시에 실행할 수 있다.

주어진 프로그램과 처리 장치 수 $k$에 대해, 최소 실행 시간을 구하라.

• 첫 줄: $n$, $q$ ($1 \leq n, q \leq 1{,}000{,}000$)
• 둘째 줄: $q$개의 정수 $k_1, \ldots, k_q$ ($1 \leq k_i \leq 1{,}000{,}000$)
• 셋째 줄: $a_2, \ldots, a_n$ ($1 \leq a_i < i$), 명령 $i$의 부모 번호. 명령 1이 루트다.

$q$개의 정수를 한 줄에 공백으로 구분해 출력한다. $i$번째 값은 $k_i$개의 처리 장치를 쓸 때의 최소 실행 시간이다.

명령 트리의 깊이별 노드 수를 전처리한 뒤, 각 $k$에 대해 "앞 $j$개 깊이를 $j$시간에 처리하고 남은 노드를 $k$개씩 처리"하는 후보들 중 최댓값을 택한다.