JOI 왕국에는 $N$개의 도시가 있으며, $1$부터 $N$까지의 번호가 붙어 있습니다. 도시 $1$은 수도입니다. 각 도시에는 활기라고 불리는 값이 정해져 있으며, 도시 $i$ ($1 \le i \le N$)의 초기 활기 값은 $C_i$입니다.
JOI 왕국의 도로는 서로 다른 두 도시를 양방향으로 연결합니다. 처음에 JOI 왕국에는 도로가 하나도 없습니다. 당신은 $N-1$번의 도로 건설을 계획했습니다. $j$번째 건설 ($1 \le j \le N-1$)은 다음과 같은 방식으로 진행될 예정입니다.
- 그 시점까지 건설된 도로만 사용하여 도시 $1$에서 도시 $A_j$로는 이동할 수 있고 도시 $1$에서 도시 $B_j$로는 이동할 수 없는 두 도시 $A_j$와 $B_j$가 지정됩니다.
당신은 도시 $A_j$와 도시 $B_j$를 연결하는 도로를 건설합니다. 이 건설의 비용은 다음 조건을 만족하는 도시의 순서쌍 $(s,t)$의 개수입니다:
도시 $s$와 도시 $t$는 도시 $1$과 도시 $A_j$ 사이의 최단 경로 위에 있으며, 도시 $1$에서 도시 $A_j$로 이동할 때 도시 $t$보다 도시 $s$에 먼저 도착하고, 도시 $s$의 활기 값이 도시 $t$의 활기 값보다 엄격하게 더 크다.
여기서 도시 $1$과 도시 $A_j$ 사이의 경로 위에 있는 도시에는 도시 $1$과 도시 $A_j$도 포함됩니다. 도시 $1$과 도시 $A_j$ 사이의 최단 경로는 유일함에 유의하십시오.
도시 $1$과 도시 $A_j$ 사이의 경로 위에 있는 모든 도시의 활기 값이 도시 $B_j$의 활기 값으로 변경됩니다.
당신은 각 도로 건설의 비용을 알고 싶습니다.
과제
도시와 도로 건설에 대한 데이터가 주어졌을 때, 각 건설의 비용을 계산하는 프로그램을 작성하십시오.
입력 형식
표준 입력에서 다음 데이터를 읽어 들이십시오.
- 입력의 첫 번째 줄에는 정수 $N$이 주어집니다. 이는 JOI 왕국에 $N$개의 도시가 있음을 의미합니다.
- 입력의 두 번째 줄에는 공백으로 구분된 $N$개의 정수 $C_1, C_2, \cdots C_N$이 주어집니다. 이는 도시 $i$ ($1 \le i \le N$)의 초기 활기 값이 $C_i$임을 의미합니다.
- 이어지는 $N-1$개의 줄 중 $j$번째 줄 ($1 \le j \le N-1$)에는 공백으로 구분된 두 정수 $A_j$, $B_j$가 주어집니다. 이는 $j$번째 도로 건설에서 도시 $A_j$와 도시 $B_j$가 지정됨을 의미합니다.
출력 형식
표준 출력에 $N-1$개의 줄을 출력하십시오. 출력의 $j$번째 줄 ($1 \le j \le N-1$)에는 $j$번째 도로 건설의 비용을 출력합니다.
제약 조건
모든 입력 데이터는 다음 조건을 만족합니다.
- $1 \le N \le 100\,000$.
- $1 \le C_i \le 1\,000\,000\,000$ ($1 \le i \le N$).
- $1 \le A_j \le N$ ($1 \le j \le N-1$).
- $1 \le B_j \le N$ ($1 \le j \le N-1$).
- $j$번째 건설 이전에 건설된 도로들을 사용하여 도시 $1$에서 도시 $A_j$로는 이동할 수 있고 도시 $1$에서 도시 $B_j$로는 이동할 수 없습니다 ($1 \le j \le N-1$).
서브태스크
총 3개의 서브태스크가 있습니다. 각 서브태스크의 점수와 추가 제약 조건은 다음과 같습니다:
서브태스크 1 [7점]
- $N \le 500$.
서브태스크 2 [9점]
- $N \le 4000$.
서브태스크 3 [84점]
추가적인 제약 조건이 없습니다.
예제
입력 1
5 1 2 3 4 5 1 2 2 3 2 4 3 5
출력 1
0 0 0 2
설명
예제 입력 1에서 건설은 다음과 같이 수행됩니다:
- 첫 번째 건설에서는 조건을 만족하는 순서쌍 $(s,t)$가 없으므로 비용은 $0$입니다. 도시 $1$과 도시 $2$를 연결하는 도로가 건설되고, 도시 $1$의 활기 값이 $2$로 변경됩니다.
- 두 번째 건설에서도 조건을 만족하는 순서쌍 $(s,t)$가 없으므로 비용은 $0$입니다. 도시 $2$와 도시 $3$을 연결하는 도로가 건설되고, 도시 $1$과 도시 $2$의 활기 값이 $3$으로 변경됩니다.
- 세 번째 건설에서도 조건을 만족하는 순서쌍 $(s,t)$가 없으므로 비용은 $0$입니다. 도시 $2$와 도시 $4$를 연결하는 도로가 건설되고, 도시 $1$과 도시 $2$의 활기 값이 $4$로 변경됩니다.
- 네 번째 건설에서는 두 순서쌍 $(s,t)=(1,3),(2,3)$이 조건을 만족하므로 비용은 $2$입니다. 도시 $3$과 도시 $5$를 연결하는 도로가 건설되고, 도시 $1$, 도시 $2$, 도시 $3$의 활기 값이 $5$로 변경됩니다.
입력 2
10 1 7 3 4 8 6 2 9 10 5 1 2 1 3 2 4 3 5 2 6 3 7 4 8 5 9 6 10
출력 2
0 0 0 1 1 0 1 2 3