Excellent Villages

A country has N villages numbered from 1 to N. The villages and roads form a tree: there are exactly N - 1 undirected roads, every road can be traveled in both directions, and every village is connected to every other village through some sequence of roads. Two villages are adjacent when there is a road directly connecting them.

To encourage the residents, some villages will be selected as excellent villages. The selection must satisfy all of the following conditions.

1. The total population of selected excellent villages must be as large as possible.
2. No two adjacent villages may both be selected as excellent villages.
3. Every village that is not selected must be adjacent to at least one selected excellent village.

Given the population of each village and the roads between villages, write a program that finds the maximum possible total population of selected excellent villages.

The first line contains an integer N (1 <= N <= 10,000).

The second line contains N natural numbers, where the i-th number is the population of village i. Each population is at most 10,000.

Each of the next N - 1 lines contains two integers, the numbers of two adjacent villages.

Print the maximum possible total population of selected excellent villages.