DMOPC '19 Contest 2 P5 - Connections

View as PDF

Submit solution


Points: 20
Time limit: 1.4s
Memory limit: 256M

Author:
Problem type

In the country of Nocrae, there exists N villages, the ith of which contains ai people. The Nocraean villages are connected to each other by N1 roads of length 1 such that it is possible to reach any village from any other village while only using these roads. The villages wish to establish a meeting place where all of the villagers can meet up. Knowing that any single village might be too far for some people to go to, the villages decided to choose two distinct villages as meeting places for the villagers to meet up. The inconvenience of each villager is defined to be the distance between his village and the closer of the two meeting places. The villagers want to know the minimum possible total inconvenience that is achievable.

Constraints

In all subtasks,
2N300000
1ai106

Subtask 1 [10%]

N100

Subtask 2 [10%]

The number of roads going to or from each village is at most 2.

Subtask 3 [30%]

N3000

Subtask 4 [50%]

No additional constraints.

Input Specification

The first line contains one integer, N.
The next line contains N space-separated integers, a1,a2,,an.
N1 lines follow, each one containing two space-separated integers, ui and vi, describing the road connecting the uith and vith villages.

Output Specification

Output one integer, the minimum possible total inconvenience.

Sample Input 1

Copy
7
3 2 1 3 2 1 3
1 3
2 4
3 5
4 6
1 7
6 5

Sample Output 1

Copy
11

Explanation for Sample Output 1

A possible choice of meeting places is villages 1 and 4. It is impossible to achieve an inconvenience lower than 11.

Sample Input 2

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

Sample Output 2

Copy
9

Explanation for Sample Output 2

A possible choice of meeting places is villages 4 and 5. It is impossible to achieve an inconvenience lower than 9.


Comments

There are no comments at the moment.