# 1. 题目

http://acm.timus.ru/problem.aspx?space=1&num=1039

## 1039. Anniversary Party

Time limit: 0.5 second
Memory limit: 8 MB

### Background

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. Employees are numbered by integer numbers in a range from 1 to N, The personnel office has ranked each employee with a conviviality rating. 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.

### Problem

Your task is to make up a guest list with the maximal conviviality rating of the guests.

### Input

The first line of the input contains a number N. 1 ≤ N ≤ 6000. Each of the subsequent N lines contains the conviviality rating of the corresponding employee. Conviviality rating is an integer number in a range from –128 to 127. After that the supervisor relation tree goes. Each line of the tree specification has the form
which means that the K-th employee is an immediate supervisor of L-th employee. Input is ended with the line

### Output

The output should contain the maximal total rating of the guests.

### Sample

input output
Problem Author: Marat Bakirov
Problem Source: Ural State University Internal Contest October’2000 Students Session

# 2. 思路

• 使用maxRating[s][0]表示不在s不参加时，以s为根的子树上的人参加年会所能获取的最大愉悦值，此时s的所有直接下属e都可以参加(maxRating[e][1])，也可以不参加(maxRating[e][0])，取决于maxRating[e][1]和maxRating[e][0]那个较大；
• 使用maxRating[s][1]表示不在s参加时，以s为根的子树上的人参加年会所能获取的最大愉悦值，此时s的所有直接下属e都不能参加（maxRating[e][0]）。