Minimum Monitoring Device Deployment

A city's road network forms a tree structure. In this tree, nodes represent intersections or endpoints and edges represent roads. There are \(n\) nodes numbered from \(1\) to \(n\). You are given the cost of installing a monitoring device at each node. Installing a device at a node monitors all roads (edges) directly connected to it. In order to monitor all roads in the city while minimizing the total installation cost, you are to determine the minimum cost needed.

Note: An edge is considered monitored if at least one of its endpoint nodes has a monitoring device installed.

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)) indicating the number of nodes. The second line contains \(n\) space-separated integers \(c_1, c_2, \dots, c_n\), where \(c_i\) is the cost for installing a device at node \(i\). Each of the following \(n-1\) lines contains two integers \(u\) and \(v\) (\(1 \le u, v \le n\)), indicating that there is an undirected road connecting nodes \(u\) and \(v\>.

outputFormat

Output a single integer, representing the minimum total cost to monitor all the roads in the city.

sample

1
10

0