题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1520
题目大意：给出n个带权点，他们的关系可以构成一棵树，问从中选出若干个不相邻的点可能得到的最大值为多少
解题思路：简单的树形DP
用dp[i][0]表示以i为根的树上不取i的状态下能得到的最大值
用dp[i][1]表示以i为根的树取i的状态下能得到的最大值
状态转移方程
dp[i][0]=∑(max(dp[son(i)][0],dp[son(i)][1]))
dp[i][1]=∑(dp[son(i)][0])+value[i]
代码如下：
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,102400000")
#define FFF 6005
int value[];
int dp[FFF][];
//dp[i][1]表示取i的最大值，dp[i][0]表示不取i的最大值
int v[FFF*],first[FFF],next[FFF*],e;
bool vis[FFF];
void link(int x,int y)
{
v[e]=y;
next[e]=first[x];
first[x]=e++;
}
int dfs(int now)
{
int ans1=,ans0=;
//ans1 取now的值 ans0 不取now的值
int k,va;
for(k=first[now];k!=-;k=next[k])
{
va=v[k];
if(!vis[va])
{
vis[va]=true;
dfs(va);
ans1+=dp[va][];
ans0+=max(dp[va][],dp[va][]);
}
}
dp[now][]=ans0;
dp[now][]=ans1+value[now];
return max(dp[now][],dp[now][]);
}
int main()
{
int n;
while(~scanf("%d",&n)){
for(int i=;i<=n;i++)
{
dp[i][]=dp[i][]=;
scanf("%d",&value[i]);
first[i]=-;
}
int x,y;
e=;
while(scanf("%d%d",&x,&y),x||y)
{
link(x,y);
link(y,x);
}
memset(vis,false,sizeof(vis));
vis[]=true;
cout<<dfs()<<endl;
}
return ;
}