고속도로 건설

시간 제한1초메모리 제한256 MB

요약

각 공사마다 1번 도시에서 A까지 경로에서 앞 도시의 활기도가 뒤 도시보다 큰 쌍의 수를 구하고, 그 경로의 활기도를 B의 활기도로 바꿉니다.

난이도: 어려움10점 중 8점
유형: 트리, 세그먼트 트리, 구간
정답자: 아직 제출이 없습니다

문제

JOI 왕국에는 1번부터 $N$ 번까지 번호가 붙은 $N$ 개의 도시가 있다. 1번 도시는 수도이다. 각 도시에는 활력(liveliness)이라는 값이 있으며, 도시 $i$ 의 초기 활력은 $C_i$ 이다.

JOI 왕국의 도로는 두 도시를 양방향으로 잇는다. 처음에는 도로가 하나도 없다. 도로 건설을 $N-1$ 번 계획하였다. $j$ 번째 건설( $1 ≤ j ≤ N-1$ )은 다음과 같이 진행한다.

도시 $A_j$ 와 도시 $B_j$ 를 고른다. 지금까지 건설된 도로만 사용했을 때 1번 도시에서 $A_j$ 로는 갈 수 있고, $B_j$ 로는 갈 수 없어야 한다.
도시 $A_j$ 와 $B_j$ 를 잇는 도로를 건설한다. 건설 비용은 도시 쌍 $(s, t)$ 의 개수이다. 이 쌍은 1번 도시에서 $A_j$ 까지의 최단 경로 위에 있고, 1번 도시에서 $A_j$ 로 갈 때 $s$ 를 $t$ 보다 먼저 지나며, $s$ 의 활력이 $t$ 의 활력보다 엄격히 큰 경우를 말한다. 경로 위의 도시에는 1번 도시와 $A_j$ 도 포함된다. 1번 도시와 $A_j$ 를 잇는 최단 경로는 하나뿐이다.
1번 도시에서 $A_j$ 까지 경로 위에 있는 모든 도시의 활력이 $B_j$ 의 활력으로 바뀐다.

각 건설의 비용을 구하라.

입력

첫째 줄에 정수 $N$ 이 주어진다. 둘째 줄에는 공백으로 구분된 정수 $C_1, C_2, ..., C_N$ 이 주어진다. 이어지는 $N-1$ 개의 줄 중 $j$ 번째 줄에는 $j$ 번째 건설에서 고르는 두 도시 $A_j$ 와 $B_j$ 가 공백으로 구분되어 주어진다.

출력

$N-1$ 개의 줄을 출력한다. $j$ 번째 줄에는 $j$ 번째 도로 건설의 비용을 출력한다.

제한

$1 ≤ N ≤ 100000$
$1 ≤ C_i ≤ 1000000000$ ( $1 ≤ i ≤ N$ )
$1 ≤ A_j ≤ N$ ( $1 ≤ j ≤ N-1$ )
$1 ≤ B_j ≤ N$ ( $1 ≤ j ≤ N-1$ )
$j$ 번째 건설 전에 건설된 도로만 사용하면 1번 도시에서 $A_j$ 로는 갈 수 있고, $B_j$ 로는 갈 수 없다( $1 ≤ j ≤ N-1$ ).

예제2

예제 1
입력
```
5
1 2 3 4 5
1 2
2 3
2 4
3 5
```
예상 출력
```
0
0
0
2
```

예제 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

예상 출력