## DMOPC '19 Contest 2 P5 - Connections

View as PDF

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

Author:
Problem type

In the country of Nocrae, there exists villages, the th of which contains people. The Nocraean villages are connected to each other by roads of length 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

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

#### Input Specification

The first line contains one integer, .
The next line contains space-separated integers,
lines follow, each one containing two space-separated integers, and , describing the road connecting the th and th villages

#### Output Specification

Output one integer, the minimum possible total inconvenience

#### Sample Input

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

#### Sample Output

11

#### Explanation for Sample Input

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

#### Sample Input 2

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

#### Sample Output 2

9

#### Explanation for Sample Input 2

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