School Network

The Ministry of Education has connected the N secondary schools in a network, consisting of N-1 communication lines. Each line connects two schools in such a way that communication between any pair of schools is feasible, either directly (via one connection) or indirectly (via multiple connections).

The school network is at risk of disruption if even one of the communication lines malfunctions. To monitor the quality of the communication lines and intervene promptly for their repair, the Ministry intends to acquire monitoring devices and place them at network nodes. Each such device will be able to monitor, from its network node, all the communication lines connected to that node.

These devices are costly, as is their placement, which may cost more or less depending on the school's location. The Ministry is interested in limiting the total cost by strategically placing the devices. You are called upon to find the minimum cost required to place devices that monitor all the lines.

Input Files:

The input file named schoolnet.in is a text file. The first line contains a single integer N, the number of schools constituting the nodes of the network. Let the schools be numbered from 1 to N. The second line contains exactly N integers, separated in pairs by a single space: the cost of placing a device for each school, in order. Each of the next N-1 lines contains exactly two integers A and B, separated by a single space, where 1 ~\le~ Α, Β ~\le~ N and Α ~\ne~ Β. This means that in the school network described in the input file, communication (direct or indirect) between any two schools is possible.

Output Files:

The output file named schoolnet.out is a text file consisting of a single line containing a single integer: the minimum possible cost for placing devices that monitor all communication lines of the network.

Example of Input - Output Files:

STDIN (schoolnet.in)

6
10 10 1 1 10 10
1 2
3 1
1 4
5 3
4 6

STDOUT (schoolnet.out)

12

Explanation: The Ministry can place devices at schools numbered 1, 3, and 4, so that all communication lines are monitored. The total cost of placing the devices is 10+1+1=12, which is the minimum possible.

Constraints:

The total sum of the placement cost for all schools will not exceed 2.000.000.000. All costs will be positive.

• For test cases worth 20%, of the total points, it will be:
  2 ≤ Ν ≤ 100
• For test cases worth 100%, of the total points, it will be:
  2 ≤ Ν ≤ 1.000.000

Formatting: In the output, each line terminates with a newline character.
Maximum execution time: 2 sec.
Maximum available memory: 64 MB.