JOI Spring Camp '18 P1 - Construction of Highway

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 \le i \le N) is C_i. Roads in JOI Kingdom connect two different cities bidirectionally. Initially, there are no roads in JOI Kingdom. You have planned N - 1 constructions of roads. The j-th construction (1 \le j \le N - 1) is planned to be done in the following way.

  • Two cities, A_j and B_j, are appointed, when one can go from city 1 to city A_j and cannot go from city 1 to city B_j by using only roads constructed at that time.
  • You construct a road connecting city A_j and city B_j. 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 A_j, and when one goes from city 1 to city A_j 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 A_j include city 1 and city A_j. Notice that the shortest path between city 1 and city A_j is unique.
  • The values of liveliness of all cities lying on the path between city 1 and city A_j change to the value of liveliness of city B_j.

You want to know the cost of each construction.

Input Specification

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 C_i. This means the initial value of liveliness of city i is C_i.

Each of following N - 1 lines contains two space separated integers A_j, B_j. This means city A_j and city B_j are appointed for the j-th construction of road. By using roads constructed before the j-th construction, one can go from city 1 to city A_j and cannot go from city 1 to city B_j (1 \le j \le N - 1).

Output Specification

Output N - 1 lines to the standard output. The j-th line (1 \le j \le N - 1) of output contains the cost of the j-th construction of road.

Constraints

All input data satisfy the following conditions.

  • 1 \le N \le 10^5
  • 1 \le C_i \le 10^9\ (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)
  • By using roads constructed before the j^{th} construction, one can go from city 1 to city A_j and cannot go from city 1 to city B_j\ (1 \le j \le N-1).
Subtask Points Additional constraints
1 7 N \le 500
2 9 N \le 4000
3 84 N \le 10^5

Sample Input 1

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

Sample Output 1

0
0
0
2

Explanation for Sample 1

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.

Sample Input 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

Sample Output 2

0
0
0
1
1
0
1
2
3

Comments

There are no comments at the moment.