35067번 - 메이플 월드 탐험하기

메이플 월드는 $N$개의 지역과 이를 양방향으로 잇는 $N - 1$개의 길로 이루어진 트리 구조이다.

각 지역 $i$에는 그 지역의 마력 수치 $A_i$가 적혀있고, 모든 지역에 적힌 마력 수치는 서로 다르다.

당신은 $i$번째 날에 다음과 같은 규칙의 탐험을 $i$번 지역부터 시작한다.

• 어떤 지역을 한 번 방문하고 다른 지역으로 이동하면, 그 지역은 붕괴되어 사라지며 다시 방문할 수 없다.
• 현재 위치한 지역에서 아직 붕괴되지 않은 인접 지역들 중 마력 수치가 가장 큰 지역으로 이동한다.
• 이동할 수 있는 인접 지역이 더 이상 없다면, 탐험은 그 지역에서 종료된다.
• 탐험이 종료되면 사라진 지역은 모두 복구되며, 다음날의 탐험에 영향을 끼치지 않는다.

모든 날에 대해 여행이 끝나는 지역이 어디인지 구하여라.

첫 번째 줄에 $N$이 주어진다. ($2 \leq N \leq 500 \,000$)

두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백으로 구분되어 주어진다. ($ 1 \leq A_i \leq N$; $i \neq j$이면 $A_i \neq A_j$)

세 번째 줄부터 $N-1$개의 줄에 걸쳐 두 지역을 잇는 길에 대한 정보 $u, v$가 공백으로 구분되어 주어진다. ($1 \leq u, v \leq N$)

첫 번째 줄부터 $N$개의 줄에 걸쳐 $i$번째 줄에는 $i$번째 날 $i$번 지역에서 여행을 시작할 경우 끝나는 지역을 출력하라.