题目大意：

给你一个树形结构，每个节点都有一个值，让你从中选取若干个店，使得点的价值和最大。注意在选取的过程中，父亲节点和儿子节点

只能选择其中的一个

INPUT:

Employees are numbered from 1 to N. A first line of input contains a number N. 1 <= N <= 6 000. 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 go T lines that describe a supervisor relation tree. Each line of the tree specification has the form: 

L K 

It means that the K-th employee is an immediate supervisor of the L-th employee. Input is ended with the line 

0 0

OUTPUT:

Output should contain the maximal sum of guests' ratings. 

SAMPLE INPUT:

  7

  1

1111111 32 36 47 44 53 50 0 SAMPLE OUTPUT: 5 这道题用最简单的树形dp就可以解决，不了解树的结构的同学可以先去学习以下树的结构。树的结构有以下几个特点： 1.两点之间存在一条边，从一个点到另一个点只有一条道路可以到达。 2.树中不存在环，如果存在环则不符合第一个特点。 因为树的特性，我们可以采用dfs的方法来对dp值进行更新。dp数组的含义如下 dp[i][0]表示第i个点不选的情况下所能获得的最大值，dp[i][1]表示第i个点选的情况下所能获得的最大值。我们可以从根节点开始向下搜索 ，状态转移方程为: dp[t][1]+=dp[son][0];//如果这个点选的话，应加上他儿子不选的情况下的值 dp[t][0]+=max(dp[son][1],dp[son][0]);//如果这点补选的话，加上他儿子选和不选的情况下的最大值 代码如下：

#include
     
      #include
      
       #include
       
        #define maxn 6000+10using namespace std;int dp[maxn][2],pre[maxn],val[maxn],n;vector
        
         q[maxn];void dfs(int t){    dp[t][1]=val[t];    for(int i=0;i
         
          >n){for(int i=1;i<=n;i++) {    cin>>val[i];    q[i].clear();    dp[i][0]=dp[i][1]=0;    pre[i]=-1;}while(true){    int a,b;    cin>>a>>b;    if(a==0&&b==0) break;    q[b].push_back(a);    pre[a]=b;    } int t=1;while(pre[t]!=-1) t=pre[t]; //这一步是为了找出根节点dfs(t);cout<
          
           <
          
         
        
       
      
     

<THEEND>