## 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]=\sum dp[j]$
$dp[i]=\sum max$($dp[j],dp[j]$)
$j$为$i$的儿子。

#include<bits/stdc++.h>
using namespace std;
int n;
int x,y;
int a;
int dp;
struct aa{
int to,nxt;
}p;
int h,len=1;
void add(int u,int v){
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;
dp[u]=a[u];
for(int j=h[u];j;j=p[j].nxt){
if(p[j].to!=fa){
dfs(p[j].to,u);
dp[u]+=max(dp[p[j].to],dp[p[j].to]);
dp[u]+=dp[p[j].to];
}
}
}
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;
add(x,y);
add(y,x);
}
dfs(1,0);
printf("%d",max(dp,dp));
return 0;
}