cho.sh

Construction of Highway

1번 도시를 루트로 하는 트리를 한 단계씩 확장하면서, 새로 붙는 경로 위에서 앞 도시의 활력이 뒤 도시보다 큰 쌍의 수를 세고 그 경로 전체의 활력을 바꾼다.

어려움8트리DFS세그먼트 트리구현아직 제출이 없습니다시간 제한1초메모리 제한256 MB

문제

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).