# 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
<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

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

### Sample

input output
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

# 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]）。

maxRating[1 : N][0 : 1] = 0
for each child e of s:
maxRating[s][0] += max(maxRating[e][1], maxRating[e][0]);
maxRating[s][1] += maxRating[e][0];

# 3. 代码

#include <cstdio>

#define MAX_N 6001

typedef struct EmployeeRecord {
int id;
struct EmployeeRecord *next;
} Employee;

void solvePE8c_AnniversaryParty();
int input(Employee *employees[], int rating[], int n);
void dfs(int id);
int max(int a, int b);

int main() {
// freopen("test.txt", "r", stdin);
solvePE8c_AnniversaryParty();
return 0;
}

Employee *employees[MAX_N];
int rating[MAX_N], maxRating[MAX_N][2];
void solvePE8c_AnniversaryParty() {
int n;
scanf("%d", &n);
int president = input(employees, rating, n);

dfs(president);

int result = max(maxRating[president][0], maxRating[president][1]);
printf("%d\n", result);
}

void dfs(int id) {
maxRating[id][0] = 0;
maxRating[id][1] = rating[id];

if (employees[id] != NULL) {
maxRating[id][0] = 0;
maxRating[id][1] = rating[id];
Employee *e = employees[id];
while (e != NULL) {
dfs(e->id);
maxRating[id][0] += max(maxRating[e->id][1], maxRating[e->id][0]);
maxRating[id][1] += maxRating[e->id][0];
e = e->next;
}
}
}

int max(int a, int b) {
return a > b ? a : b;
}

bool isEmployee[MAX_N];
int input(Employee *employees[], int rating[], int n) {
for (int i = 1; i <= n; ++i) {
scanf("%d", &rating[i]);
}

int employee, superv;
scanf("%d %d", &employee, &superv);
while (employee != 0) {
Employee *e = new Employee();
e->id = employee;
e->next = employees[superv];
employees[superv] = e;
isEmployee[employee] = true;

scanf("%d %d", &employee, &superv);
}

for (int i = 1; i <= n; ++i) {
if (!isEmployee[i]) {
return i;
}
}

return -1;
}