DMOPC '19 Contest 2 P5 - Connections

View as PDF

Submit solution

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

Problem type

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


In all subtasks,
2 \le N \le 300\,000
1 \le a_i \le 10^6

Subtask 1 [10%]

N \le 100

Subtask 2 [10%]

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

Subtask 3 [30%]

N \le 3\,000

Subtask 4 [50%]

No additional constraints.

Input Specification

The first line contains one integer, N.
The next line contains N space-separated integers, a_1, a_2, \dots, a_n.
N-1 lines follow, each one containing two space-separated integers, u_i and v_i, describing the road connecting the u_ith and v_ith villages.

Output Specification

Output one integer, the minimum possible total inconvenience.

Sample Input 1

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

Sample Output 1


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

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

Sample Output 2


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.


There are no comments at the moment.