문제 설명
\(1\)번 정점부터 \(N\)번 정점까지 \(N\)개의 정점으로 이루어진 루트 있는 트리가 있다. 이 트리의 루트 정점은 \(1\) 번 정점이고, \(i\)번 정점의 부모 정점은 \(P_i\)번 정점이다\((2 \le i \le N)\). 또한 각 정점은 서로 다른 정수 가중치를
갖고 있다. 이때 \(i\)번 정점의 가중치는 \(A_i\)이다\((1 \le i \le N)\). 자식을 가지지 않은 정점을 리프 정점이라고 한다.
루트 정점인 \(1\)번 정점에서 출발하여 자식 중에 가중치가 가장 작은 정점으로 이동하는 것을 반복하자. 리프 정점에 도달할 때까지 이를 반복하면 \(1\)번 정점에서 시작하여 리프 정점에서 끝나는 경로 \(S\)를 얻을 수 있다. 이때 \(S = {S_1, · · · , S_k}\)를 특별한 경로라고 정의한다.
또한, 뽑아내기 연산을 다음과 같이 정의한다.
예를 들어, 아래와 같은 트리들을 생각하자. 원 밖의 수는 정점의 번호를 나타내고, 원 안의 수는 그 정점의 가중치를 나타낸다.
첫 번째 트리의 특별한 경로를 찾아보자. 루트 정점인 \(1\)번 정점에서 출발하여 \(1\)번 정점의 자식 중 가중치 가 가장 작은 \(3\)번 정점으로 이동하고, \(3\)번 정점의 자식 중 가중치가 가장 작은 \(4\)번 정점으로 이동한다. \(4\)번 정점은 리프 정점이기 때문에 특별한 경로가 \(S = {1, 3, 4}\)임을 알 수 있다. 이제 이 트리에 뽑아내기 연산을 적용하면 \(1\)번 정점과 \(3\)번 정점의 가중치를 교환하고, \(3\)번 정점과 \(4\)번 정점의 가중치를 교환한 뒤 \(4\)번 정점을 트리에서 제거하여 두 번째 트리와 같은 모양이 된다.
두 번째 트리의 특별한 경로를 찾아보자. 루트 정점인 \(1\)번 정점에서 시작하여 \(1\)번 정점의 자식 중 가중치가 가장 작은 \(2\)번 정점으로 이동한다. \(2\)번 정점이 리프 정점이기 때문에 특별한 경로가 \(S = {1, 2}\)임을 알 수 있다. 이제 이 트리에 뽑아내기 연산을 적용하면 \(1\)번 정점과 \(2\)번 정점의 가중치를 교환한 뒤 \(2\)번 정점을 트리에서 제거하여 세 번째 트리와 같은 모양이 된다.
세 번째 트리의 특별한 경로를 찾아보자. 루트 정점인 \(1\)번 정점에서 시작하여 \(1\)번 정점의 유일한 자식인 \(3\) 번 정점으로 이동하고, \(3\)번 정점의 유일한 자식인 \(5\)번 정점으로 이동한다. \(5\)번 정점이 리프 정점이기 때문에 특별한 경로가 \(S = {1, 3, 5}\)임을 알 수 있다. 이제 이 트리에 뽑아내기 연산을 적용하면 \(1\)번 정점과 \(3\)번 정점의 가중치를 교환하고, \(3\)번 정점과 \(5\)번 정점의 가중치를 교환한 뒤 \(5\)번 정점을 트리에서 제거하여 네 번째 트리와 같은 모양이 된다.
마찬가지로 네 번째 트리의 특별한 경로는 \(S = {1, 3}\)이다. 이 트리에 뽑아내기 연산을 적용하면 \(1\)번 정점과 \(3\)번 정점의 가중치를 교환한 뒤 \(3\)번 정점을 트리에서 제거하여 다섯 번째 트리와 같은 모양이 된다
마지막으로 다섯 번째 트리의 특별한 경로는 \(S = {1}\)이며, 뽑아내기 연산을 적용하면 \(1\)번 정점이 트리에서 제거된다.
이와 같이 우리는 주어진 트리에 뽑아내기 연산을 \(N\)번 수행하려고 한다. 이때, 각 뽑아내기 연산을 수행 하기 전에 \(1\)번 정점에 적혀 있던 가중치의 값을 모두 구하는 프로그램을 작성하라.
제약 조건
• 주어지는 모든 수는 정수이다.
• \(2 \le N \le 300 000\)
• \(1 \le P_i < i (2 \le i \le N)\)
• \(1 \le A_i \le N (1 \le i \le N)\)
• \(A_1, · · · , A_N\)은 서로 다르다.
부분 문제
1. (6점) \(N \le 3 000\)
2. (10점) \(2 \le i \le N\)를 만족하는 모든 \(i\)에 대해 \(A_{P_i} < A_i\)이다.
3. (11점) \(2 \le i \le N\)를 만족하는 모든 \(i\)에 대해 \(A_{P_i} > A_i\)이다.
4. (23점) 차수가 \(3\) 이상인 정점의 수가 \(20\)개 이하이다.
5. (50점) 추가 제약 조건 없음
루트 정점인 \(1\)번 정점에서 출발하여 자식 중에 가중치가 가장 작은 정점으로 이동하는 것을 반복하자. 리프 정점에 도달할 때까지 이를 반복하면 \(1\)번 정점에서 시작하여 리프 정점에서 끝나는 경로 \(S\)를 얻을 수 있다. 이때 \(S = {S_1, · · · , S_k}\)를 특별한 경로라고 정의한다.
또한, 뽑아내기 연산을 다음과 같이 정의한다.
- 뽑아내기:
- 현재 트리의 특별한 경로가 \(S = {S_1, · · · , S_k}\)이라고 하자.
- \(S_1\)번 정점과 \(S_2\)번 정점의 가중치를 교환한다.
- \(S_2\)번 정점과 \(S_3\)번 정점의 가중치를 교환한다.
- · · ·
- \(S_{k−1}\)번 정점과 \(S_k\)번 정점의 가중치를 교환한다.
- \(S_k\)번 정점과 그 부모를 잇는 간선을 트리에서 제거한다.
예를 들어, 아래와 같은 트리들을 생각하자. 원 밖의 수는 정점의 번호를 나타내고, 원 안의 수는 그 정점의 가중치를 나타낸다.
첫 번째 트리의 특별한 경로를 찾아보자. 루트 정점인 \(1\)번 정점에서 출발하여 \(1\)번 정점의 자식 중 가중치 가 가장 작은 \(3\)번 정점으로 이동하고, \(3\)번 정점의 자식 중 가중치가 가장 작은 \(4\)번 정점으로 이동한다. \(4\)번 정점은 리프 정점이기 때문에 특별한 경로가 \(S = {1, 3, 4}\)임을 알 수 있다. 이제 이 트리에 뽑아내기 연산을 적용하면 \(1\)번 정점과 \(3\)번 정점의 가중치를 교환하고, \(3\)번 정점과 \(4\)번 정점의 가중치를 교환한 뒤 \(4\)번 정점을 트리에서 제거하여 두 번째 트리와 같은 모양이 된다.
두 번째 트리의 특별한 경로를 찾아보자. 루트 정점인 \(1\)번 정점에서 시작하여 \(1\)번 정점의 자식 중 가중치가 가장 작은 \(2\)번 정점으로 이동한다. \(2\)번 정점이 리프 정점이기 때문에 특별한 경로가 \(S = {1, 2}\)임을 알 수 있다. 이제 이 트리에 뽑아내기 연산을 적용하면 \(1\)번 정점과 \(2\)번 정점의 가중치를 교환한 뒤 \(2\)번 정점을 트리에서 제거하여 세 번째 트리와 같은 모양이 된다.
세 번째 트리의 특별한 경로를 찾아보자. 루트 정점인 \(1\)번 정점에서 시작하여 \(1\)번 정점의 유일한 자식인 \(3\) 번 정점으로 이동하고, \(3\)번 정점의 유일한 자식인 \(5\)번 정점으로 이동한다. \(5\)번 정점이 리프 정점이기 때문에 특별한 경로가 \(S = {1, 3, 5}\)임을 알 수 있다. 이제 이 트리에 뽑아내기 연산을 적용하면 \(1\)번 정점과 \(3\)번 정점의 가중치를 교환하고, \(3\)번 정점과 \(5\)번 정점의 가중치를 교환한 뒤 \(5\)번 정점을 트리에서 제거하여 네 번째 트리와 같은 모양이 된다.
마찬가지로 네 번째 트리의 특별한 경로는 \(S = {1, 3}\)이다. 이 트리에 뽑아내기 연산을 적용하면 \(1\)번 정점과 \(3\)번 정점의 가중치를 교환한 뒤 \(3\)번 정점을 트리에서 제거하여 다섯 번째 트리와 같은 모양이 된다
마지막으로 다섯 번째 트리의 특별한 경로는 \(S = {1}\)이며, 뽑아내기 연산을 적용하면 \(1\)번 정점이 트리에서 제거된다.
이와 같이 우리는 주어진 트리에 뽑아내기 연산을 \(N\)번 수행하려고 한다. 이때, 각 뽑아내기 연산을 수행 하기 전에 \(1\)번 정점에 적혀 있던 가중치의 값을 모두 구하는 프로그램을 작성하라.
제약 조건
• 주어지는 모든 수는 정수이다.
• \(2 \le N \le 300 000\)
• \(1 \le P_i < i (2 \le i \le N)\)
• \(1 \le A_i \le N (1 \le i \le N)\)
• \(A_1, · · · , A_N\)은 서로 다르다.
부분 문제
1. (6점) \(N \le 3 000\)
2. (10점) \(2 \le i \le N\)를 만족하는 모든 \(i\)에 대해 \(A_{P_i} < A_i\)이다.
3. (11점) \(2 \le i \le N\)를 만족하는 모든 \(i\)에 대해 \(A_{P_i} > A_i\)이다.
4. (23점) 차수가 \(3\) 이상인 정점의 수가 \(20\)개 이하이다.
5. (50점) 추가 제약 조건 없음
입력 설명
첫 번째 줄에 정수 \(N\)이 주어진다.
두 번째 줄에 \(N − 1\)개의 정수 \(P_2, · · · , P_N\)이 공백을 사이에 두고 주어진다.
세 번째 줄에 \(N\)개의 정수 \(A_1, · · · , A_N\)이 공백을 사이에 두고 주어진다.
두 번째 줄에 \(N − 1\)개의 정수 \(P_2, · · · , P_N\)이 공백을 사이에 두고 주어진다.
세 번째 줄에 \(N\)개의 정수 \(A_1, · · · , A_N\)이 공백을 사이에 두고 주어진다.
출력 설명
첫 번째 줄부터 \(N\)개의 줄에 걸쳐 답을 출력한다. 이 중 \(i(1 \le i \le N)\)번째 줄에는 \(i\)번째 뽑아내기 연산을
수행하기 전 \(1\)번 정점에 적혀 있던 가중치의 값을 출력한다.
입력 예시 Copy
5
1 1 3 3
5 2 1 3 4
출력 예시 Copy
5
1
2
3
4
도움
(중4,고3)