树形dp（HDU1520）

HDU-1520 Anniversary party

题目大意：

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

只能选择其中的一个

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:

1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 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<iostream>
#include<vector>
#include<cmath>
#define maxn 6000+10
using namespace std;
int dp[maxn][2],pre[maxn],val[maxn],n;
vector<int >q[maxn];
void dfs(int t)
{
    dp[t][1]=val[t];
    for(int i=0;i<q[t].size();i++)
    {
         int son=q[t][i];
         dfs(son);
         dp[t][1]+=dp[son][0];
         dp[t][0]+=max(dp[son][1],dp[son][0]);
    } 
}
int main()
{
while(cin>>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<<max(dp[t][0],dp[t][1])<<endl; //输出根节点选与不选情况下的最大值
}
  return 0;    
}