Maximum Happiness at the Annual Party

There is a university with \( n \) employees numbered from \( 1 \) to \( n \). Their hierarchical structure forms a tree with the principal as the root. Each employee \( i \) contributes a happiness index \( r_i \) if invited to the annual party. However, if an employee's direct superior is invited, then that employee will refuse to attend.

Your task is to choose a set of employees to invite so that the total happiness index is maximized, subject to the constraint that no employee attends alongside their direct superior.

inputFormat

The first line contains an integer \( n \) \( (1 \le n \le 10^5) \), the number of employees.

The second line contains \( n \) integers \( r_1, r_2, \ldots, r_n \), where \( r_i \) is the happiness index of the \( i \)-th employee.

Each of the following \( n-1 \) lines contains two integers \( u \) and \( v \), indicating that employee \( u \) is the direct superior of employee \( v \).

outputFormat

Output a single integer representing the maximum total happiness index that can be achieved by inviting a proper subset of employees under the given constraints.

sample

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

12