HDRF

빅데이터를 다룬다면 코드를 분산 방식으로 실행하는 일에 익숙해야 한다. 병렬 계산을 가능하게 하려면 많은 인프라 요소가 함께 동작해야 한다. 그중 하나가 보통 스케줄러이며, 스케줄러는 지금 시작할 작업을 공정하면서도 효율적인 방식으로 고른다.

작업은 성격(테스트, 장시간 실행, 실시간 등)에 따라 계층 구조로 묶인다. 이 계층 구조는 루트가 있는 트리로 나타낼 수 있다.

다음 문제는 최신 스케줄링 알고리즘인 계층적 지배 자원 공정성(HDRF)에서 영감을 받았다.

루트가 정점 1인 트리 $T$가 주어진다. $T$는 $n$개의 정점으로 이루어져 있다. 각 정점 $i$에는 서로 다른 우선순위 $v_i$가 있다. 각 정점 $i$에 대해 $r_i$를 정점 $i$ 자신을 포함한 서브트리에 있는 $v$ 값 중 가장 작은 값으로 정의한다.

다음 순회 알고리즘을 생각하자.

• 루트 정점에서 시작한다.
• 현재 정점의 직계 자식 중 $r$ 값이 가장 작은 자식을 고른다.
• 그 자식으로 이동한다.
• 현재 정점이 리프이면 그 정점을 기록하고 트리에서 제거한다. 정점을 제거하면 모든 $r_i$를 다시 계산한다. 리프가 아니면 2번 단계로 돌아간다.

트리가 빌 때까지 1번 단계부터 이 과정을 반복한다.

트리 $T$와 값 $v_i$가 주어졌을 때, 알고리즘이 정점을 기록하는 순서를 구하라.

첫 줄에 정수 $n$ ($2 \leq n \leq 100\,000$)이 주어진다. 트리의 정점 개수이다.

둘째 줄에는 $n - 1$개의 정수가 주어진다. $i$번째 정수 $p_i$ ($1 \leq p_i \leq n$)는 정점 $i + 1$의 부모이다. 정점은 1부터 $n$까지 번호가 매겨진다. 입력은 루트가 정점 1인 유효한 루트 트리임이 보장된다.

셋째 줄에는 $n$개의 서로 다른 정수 $v_1, v_2, \ldots, v_n$ ($0 \leq v_i \leq 10^9$)이 주어진다. 각 정점의 우선순위이다.

알고리즘이 정점을 기록하는 순서대로 $n$개의 정점을 출력한다.