## Anniversary Party

### 题目背景

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.

### 题目描述

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

### 输入格式

The first line of the input contains a number $N$. $1 \le N \le 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$

### 输出格式

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

### 样例输入

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0


### 样例输出

5


## 题解

$dp[i][1]=\sum dp[j][0]$
$dp[i][0]=\sum max$($dp[j][0],dp[j][1]$)
$j$为$i$的儿子。

#include<bits/stdc++.h>
using namespace std;
int n;
int x,y;
int a[6009];
int dp[6009][2];
struct aa{
int to,nxt;
}p[20009];
int h[6009],len=1;
p[++len].to=v;
p[len].nxt=h[u];
h[u]=len;
}
void dfs(int u,int fa){
int sum=0,ss=0;
dp[u][0]=0;
dp[u][1]=a[u];
for(int j=h[u];j;j=p[j].nxt){
if(p[j].to!=fa){
dfs(p[j].to,u);
dp[u][0]+=max(dp[p[j].to][0],dp[p[j].to][1]);
dp[u][1]+=dp[p[j].to][0];
}
}
}
int main(){
scanf("%d",&n);
for(int j=1;j<=n;j++)
scanf("%d",&a[j]);
while(1){
scanf("%d%d",&x,&y);
if(x==0 && y==0) break;
}