ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Championship 2000

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Anniversary Party

Time limit: 0.5 second
Memory limit: 8 MB
The president of the Ural State University is going to make an 80'th Anniversary party. The university has a hierarchical structure of employees; that is, the supervisor relation forms a tree rooted at the president. In order to make the party fun for all attendees, the president does not want both an employee and his or her immediate supervisor to attend.
The personnel office has ranked each employee with a conviviality rating. Your task is to make up a guest list with the maximal conviviality rating of the guests.

Input

The first line contains an integer N that is a number of employees (1 ≤ N ≤ 6000). Employees are numbered by integers in a range from 1 to N, Each of the subsequent N lines contains the conviviality rating of the corresponding employee. Conviviality rating is an integer in a range from −128 to 127. After that the supervisor relation tree goes. Each line of the tree specification has the form
<L> <K>
which means that the K-th employee is an immediate supervisor of L-th employee. Input is ended with the line
0 0

Output

Output the maximal total conviviality rating of the guests.

Sample

inputoutput
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
5
Problem Author: Marat Bakirov
Problem Source: Ural State University Internal Contest October'2000 Students Session
To submit the solution for this problem go to the Problem set: 1039. Anniversary Party