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, \cdots, S_k}를 특별한 경로라고 정의한다.

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

뽑아내기:
- 현재 트리의 특별한 경로가 S = {S_1, \cdots, S_k}이라고 하자.
- S_1번 정점과 S_2번 정점의 가중치를 교환한다.
- S_2번 정점과 S_3번 정점의 가중치를 교환한다.
- \cdots
- 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, \cdots, A_N은 서로 다르다.

#8019 upload 118 done 60 how_to_reg 55 call_split サブタスク

트리 뽑아내기 timer 2s memory 1024MB

#8019
サブタスク

트리 뽑아내기 2s 1024MB