루미 알고리즘

#1103다이아트리 뽑아내기트리 뽑아내기

KOI 2024 2차코딩중등부 4번, 고등부 3번출제 이온조이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

트리 뽑아내기

원제: 트리 뽑아내기

문제

11번 정점부터 NN번 정점까지 NN개의 정점으로 이루어진 루트 있는 트리가 있다. 이 트리의 루트 정점은 11번 정점이고, ii번 정점의 부모 정점은 PiP_i번 정점이다(2≤i≤N2 \le i \le N). 또한 각 정점은 서로 다른 정수 가중치를 갖고 있다. 이때 ii번 정점의 가중치는 AiA_i이다(1≤i≤N1 \le i \le N). 자식을 가지지 않은 정점을 리프 정점이라고 한다.

루트 정점인 11번 정점에서 출발하여 자식 중에 가중치가 가장 작은 정점으로 이동하는 것을 반복하자. 리프 정점에 도달할 때까지 이를 반복하면 11번 정점에서 시작하여 리프 정점에서 끝나는 경로 SS를 얻을 수 있다. 이때 S={S1,⋯ ,Sk}S = \{S_1, \cdots, S_k\}를 특별한 경로라고 정의한다.

또한, 뽑아내기 연산을 다음과 같이 정의한다.

  • 뽑아내기:
    • 현재 트리의 특별한 경로가 S={S1,⋯ ,Sk}S = \{S_1, \cdots, S_k\}이라고 하자.
    • S1S_1번 정점과 S2S_2번 정점의 가중치를 교환한다.
    • S2S_2번 정점과 S3S_3번 정점의 가중치를 교환한다.
    • ⋯\cdots
    • Sk−1S_{k-1}번 정점과 SkS_k번 정점의 가중치를 교환한다.
    • SkS_k번 정점과 그 부모를 잇는 간선을 트리에서 제거한다.

즉, 뽑아내기 연산은 특별한 경로 위에 있는 정점들의 가중치를 경로 상에서 자신 다음에 등장하는 정점의 가중치로 수정하고, 특별한 경로의 마지막에 위치한 리프 정점을 제거하는 연산이다.

예를 들어, 아래와 같은 트리들을 생각하자. 원 밖의 수는 정점의 번호를 나타내고, 원 안의 수는 그 정점의 가중치를 나타낸다.

(그림은 원문 PDF 탭에서 볼 수 있습니다.)

첫 번째 트리의 특별한 경로를 찾아보자. 루트 정점인 11번 정점에서 출발하여 11번 정점의 자식 중 가중치가 가장 작은 33번 정점으로 이동하고, 33번 정점의 자식 중 가중치가 가장 작은 44번 정점으로 이동한다. 44번 정점은 리프 정점이기 때문에 특별한 경로가 S={1,3,4}S = \{1, 3, 4\}임을 알 수 있다. 이제 이 트리에 뽑아내기 연산을 적용하면 11번 정점과 33번 정점의 가중치를 교환하고, 33번 정점과 44번 정점의 가중치를 교환한 뒤 44번 정점을 트리에서 제거하여 두 번째 트리와 같은 모양이 된다.

두 번째 트리의 특별한 경로를 찾아보자. 루트 정점인 11번 정점에서 시작하여 11번 정점의 자식 중 가중치가 가장 작은 22번 정점으로 이동한다. 22번 정점이 리프 정점이기 때문에 특별한 경로가 S={1,2}S = \{1, 2\}임을 알 수 있다. 이제 이 트리에 뽑아내기 연산을 적용하면 11번 정점과 22번 정점의 가중치를 교환한 뒤 22번 정점을 트리에서 제거하여 세 번째 트리와 같은 모양이 된다.

세 번째 트리의 특별한 경로를 찾아보자. 루트 정점인 11번 정점에서 시작하여 11번 정점의 유일한 자식인 33번 정점으로 이동하고, 33번 정점의 유일한 자식인 55번 정점으로 이동한다. 55번 정점이 리프 정점이기 때문에 특별한 경로가 S={1,3,5}S = \{1, 3, 5\}임을 알 수 있다. 이제 이 트리에 뽑아내기 연산을 적용하면 11번 정점과 33번 정점의 가중치를 교환하고, 33번 정점과 55번 정점의 가중치를 교환한 뒤 55번 정점을 트리에서 제거하여 네 번째 트리와 같은 모양이 된다.

마찬가지로 네 번째 트리의 특별한 경로는 S={1,3}S = \{1, 3\}이다. 이 트리에 뽑아내기 연산을 적용하면 11번 정점과 33번 정점의 가중치를 교환한 뒤 33번 정점을 트리에서 제거하여 다섯 번째 트리와 같은 모양이 된다.

마지막으로 다섯 번째 트리의 특별한 경로는 S={1}S = \{1\}이며, 뽑아내기 연산을 적용하면 11번 정점이 트리에서 제거된다.

이와 같이 우리는 주어진 트리에 뽑아내기 연산을 NN번 수행하려고 한다. 이때, 각 뽑아내기 연산을 수행하기 전에 11번 정점에 적혀 있던 가중치의 값을 모두 구하는 프로그램을 작성하라.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 2≤N≤300 0002 \le N \le 300\,000
  • 1≤Pi<i1 \le P_i < i (2≤i≤N)(2 \le i \le N)
  • 1≤Ai≤N1 \le A_i \le N (1≤i≤N)(1 \le i \le N)
  • A1,⋯ ,ANA_1, \cdots, A_N은 서로 다르다.

부분문제

  1. (6점) N≤3 000N \le 3\,000
  2. (10점) 2≤i≤N2 \le i \le N를 만족하는 모든 ii에 대해 APi<AiA_{P_i} < A_i이다.
  3. (11점) 2≤i≤N2 \le i \le N를 만족하는 모든 ii에 대해 APi>AiA_{P_i} > A_i이다.
  4. (23점) 차수가 33 이상인 정점의 수가 2020개 이하이다.
  5. (50점) 추가 제약 조건 없음.

입력 형식

첫 번째 줄에 정수 NN이 주어진다.

두 번째 줄에 N−1N - 1개의 정수 P2,⋯ ,PNP_2, \cdots, P_N이 공백을 사이에 두고 주어진다.

세 번째 줄에 NN개의 정수 A1,⋯ ,ANA_1, \cdots, A_N이 공백을 사이에 두고 주어진다.

출력 형식

첫 번째 줄부터 NN개의 줄에 걸쳐 답을 출력한다. 이 중 i(1≤i≤N)i(1 \le i \le N)번째 줄에는 ii번째 뽑아내기 연산을 수행하기 전 11번 정점에 적혀 있던 가중치의 값을 출력한다.

예제

예제 1

입력
5
1 1 3 3
5 2 1 3 4
출력
5
1
2
3
4

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2024년 2차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.