시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB39242074.074%

문제

There are N cities in JOI Kingdom, which are indexed by the numbers from 1 to N. City 1 is the capital city. Each city has a value called liveliness and the initial value of liveliness of city i (1 ≤ i ≤ N) is Ci.

Road in JOI Kingdom connects two different cities bidirectionally. Initially, there is no road in JOI Kingdom. You have planned N − 1 constructions of roads. The j-th construction (1 ≤ j ≤ N − 1) is planned to be done in the follwing way.

  • Two cities, Aj and Bj, are appointed, when one can go from city 1 to city Aj and cannot go from city 1 to city Bj by using only roads constructed at that time.
  • You construct a road connecting city Aj and city Bj. The cost of this construction is the number of pairs of cities (s, t) satisfying the following conditions:
    • City s and City t lie on the shortest path between city 1 and city Aj, and when one goes from city 1 to city Aj he arrives city s before city t, and the value of liveliness of city s is strictly larger than that of city t. Here, cities lying on the path between city 1 and city Aj include city 1 and city Aj. Notice that the shortest path between city 1 and city Aj is unique.
  • The values of liveliness of all cities lying on the path between city 1 and city Aj change to the value of liveliness of city Bj.

You want to know the cost of each construction.

Given the data of cities and constructions of roads, write a program which calculates the cost of each construction.

입력

Read the following data from the standard input.

  • The first line of input contains a integer N. This means there are N cities in JOI Kingdom.
  • The second line of input contains N space separated integers C1, C2, · · ·, CN. This means the initial value of liveliness of city i (1 ≤ i ≤ N) is Ci.
  • The j-th line (1 ≤ j ≤ N − 1) of following N − 1 lines contains two space separated integers Aj, Bj. This means city Aj and city Bj are appointed for the j-th construction of road.

출력

Write N − 1 lines to the standard output. The j-th line (1 ≤ j ≤ N − 1) of output contains the cost of the j-th construction of road.

제한

  • 1 ≤ N ≤ 100 000.
  • 1 ≤ Ci ≤ 1 000 000 000 (1 ≤ i ≤ N).
  • 1 ≤ Aj ≤ N (1 ≤ j ≤ N − 1).
  • 1 ≤ Bj ≤ N (1 ≤ j ≤ N − 1).
  • By using roads constructed before the j-th construction, one can go from city 1 to city Aj and cannot go from city 1 to city Bj (1 ≤ j ≤ N − 1).

서브태스크

번호배점제한
17

N ≤ 500.

29

N ≤ 4000.

384

There are no additional constraints.

예제 입력 1

5
1 2 3 4 5
1 2
2 3
2 4
3 5

예제 출력 1

0
0
0
2

In Sample Input 1, constructions are done as follows:

  • In the first construction, there are no pairs (s, t) satisfying the conditions, so the cost is 0. A road connecting city 1 and city 2 is constructed and the value of liveliness of city 1 changes to 2.
  • In the second construction, there are no pairs (s, t) satisfying the conditions too, so the cost is 0. A road connecting city 2 and city 3 is constructed and the values of liveliness of city 1 and city 2 change to 3.
  • In the third construction, there are no pairs (s, t) satisfying the conditions too, so the cost is 0. A road connecting city 2 and city 4 is constructed and the values of liveliness of city 1 and city 2 change to 4.
  • In the fourth construction, two pairs (s, t) = (1, 3), (2, 3) satisfy the conditions, so the cost is 2. A road connecting city 3 and city 5 is constructed and the values of liveliness of city 1, city 2 and city 3 change to 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

채점 및 기타 정보

  • 예제는 채점하지 않는다.