（树形DP入门题）Anniversary party（没有上司的舞会） HDU – 1520

题意：

有个公司要举行一场晚会。为了让到会的每个人不受他的直接上司约束而能玩得开心，公司领导决定：如果邀请了某个人，那么一定不会再邀请他的直接的上司，但该人的上司的上司，上司的上司的上司等都可以邀请。已知每个人最多有唯一的一个上司。 
已知公司的每个人参加晚会都能为晚会增添一些气氛，求一个邀请方案，使气氛值的和最大。

思路：

树形DP入门题

①先设定：数组dp[i][0]为第i个人参加了舞会的时候这个子树的欢乐值之和

                  数组dp[i][1]为第i个人没参加舞会的时候这个子树的欢乐值之和

②由此我们可以推出对于i的状态转移方程为

　　          dp[i][0] = a[i]+ ∑dp[j][1]  (i为j的父亲节点)  

　　　　dp[i][1] = ∑Max(dp[j][1],dp[j][0])  (i为j的父亲节点)

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
 using namespace std;
 const int maxn=;
 int a[maxn],dp[maxn][];
 int n;
 vector<int> edge[maxn];
 void dfs(int x,int fa)
 {
     dp[x][]=a[x],dp[x][]=;
     for(int i=;i<edge[x].size();i++){
         if(edge[x][i]!=fa){
             dfs(edge[x][i],x);
             dp[x][]+=dp[edge[x][i]][];
             dp[x][]+=max(dp[edge[x][i]][],dp[edge[x][i]][]);
         }
     }
 }
 int main()
 {
     while(scanf("%d",&n)!=EOF){
         for(int i=;i<=n;i++)
             scanf("%d",&a[i]);
         int l,k;
         for(int i=;i<=n;i++)
             edge[i].clear();
         memset(dp,,sizeof(dp));
         while(scanf("%d%d",&l,&k)&&l&&k){
             edge[l].push_back(k);
             edge[k].push_back(l);
         }
        dfs(,);
        printf("%d\n",max(dp[][],dp[][]));
     }
    return ;
 }