Anniversary party
题目链接：
http://poj.org/problem?id=2342
题意：给定每个人的快乐值，邀请一部分人去参加宴会，被邀请的人和该人的上司只能去一个，使得最终的快乐值最大。
应该是一道很简单的树dp吧，正在学习当中 ~ing，树dp，紫薯上的最大独立集啊。
包括两部分，建树部分和dp部分，，，建树、、、、、和dp（找到转移方程啊）
用1，0分别表示去和不去的状态，dp[i][0],dp[i][1],到第i位上司为止的最大的快乐值（这个人去或不去）。
dp[u][1]+=dp[v][0]; //上司去，下属不去
dp[u][0]+=max(dp[v][0],dp[v][1]);//上司不去，下属去或不去的最大值
用dfs依次递归，如果dfs(1,-1)则是从1开始，最终返回到最大值在1,处，如果dfs(n,-1)开始，最终返回到n处最大值，理解递归。
参考代码：
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <iostream>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=6010;
struct Edge
{
int v,next;
}edge[maxn*2];
int n,k,cnt[maxn],head[maxn],dp[maxn][2];
void add_edge(int u,int v)
{
edge[k].v=v;
edge[k].next=head[u];
head[u]=k++;
}
void dfs(int u,int fa)
{
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(v!=fa)
{
dfs(v,u);
dp[u][1]+=dp[v][0]; //去
dp[u][0]+=max(dp[v][0],dp[v][1]);//不去
}
}
}
int main()
{
//freopen("C:\\Users\\Administrator\\Desktop\\a.txt","r",stdin);
k=0;
int a,b;
for(int i=0;i<maxn;i++)
head[i]=-1,dp[i][0]=0,dp[i][1]=0;
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++)
scanf("%d",&dp[i][1]);
while(scanf("%d%d",&a,&b),a&&b)
add_edge(a,b),add_edge(b,a);
dfs(1,-1);
cout<<max(dp[1][0],dp[1][1])<<endl;
}
return 0;
}
