#PQJ1546x114. QOJ 1546_114

    ID: 2640 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2021 集训最短路

QOJ 1546_114

The 17th Japanese Olympiad in Informatics (JOI 2017/2018) Spring Training Camp/Qualifying Trial March 19–25, 2018 (Komaba/Yoyogi, Tokyo) Contest Day 1 – Construction of Highway Construction of Highway 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, A j and Bj, are appointed, when one can go from city 1 to city A j and cannot go from city 1 to city Bj by using only roads constructed at that time. • You construct a road connecting city A j 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 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 Bj. You want to know the cost of each construction. Task Given the data of cities and constructions of roads, write a program which calculates the cost of each construc- tion. Input 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 A j, Bj. This means city A j and city Bj are appointed for the j-th construction of road. Construction of Highway– 1 / 3 The 17th Japanese Olympiad in Informatics (JOI 2017/2018) Spring Training Camp/Qualifying Trial March 19–25, 2018 (Komaba/Yoyogi, Tokyo) Contest Day 1 – Construction of Highway Output 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. Constraints All input data satisfy the following conditions. • 1 ≤N ≤100 000. • 1 ≤Ci ≤1 000 000 000 (1 ≤i ≤N). • 1 ≤A j ≤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 A j and cannot go from city 1 to city Bj (1 ≤j ≤N −1). Subtask There are 3 subtasks. The score and additional constraints of each subtask are as follows: Subtask 1 [7 points] • N ≤500. Subtask 2 [9 points] • N ≤4000. Subtask 3 [84 points] There are no additional constraints. Construction of Highway– 2 / 3 The 17th Japanese Olympiad in Informatics (JOI 2017/2018) Spring Training Camp/Qualifying Trial March 19–25, 2018 (Komaba/Yoyogi, Tokyo) Contest Day 1 – Construction of Highway Sample Input and Output Sample Input 1 Sample Output 1 5 0 1 2 3 4 5 0 1 2 0 2 3 2 2 4 3 5 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 Sample Output 2 10 0 1 7 3 4 8 6 2 9 10 5 0 1 2 0 1 3 1 2 4 1 3 5 0 2 6 1 3 7 2 4 8 3 5 9 6 10 Construction of Highway– 3 / 3