考虑取和不去 dp[u][0]代表u为根的树不取 儿子v可以取可以不取dp[u][1]代表取u 然后儿子v不能取 水题1A
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 6010;
vector <int> G[maxn];
double dp[maxn][2];
int a[maxn];
int in[maxn];
int n;
void dfs(int u)
{
dp[u][1] = a[u];
for(int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];
dfs(v);
dp[u][0] += max(dp[v][0], dp[v][1]);
dp[u][1] += dp[v][0];
}
}
int main()
{
int n;
while(scanf("%d", &n) != EOF)
{
for(int i = 1; i <= n; i++)
{
G[i].clear();
in[i] = 0;
scanf("%d", &a[i]);
}
int u, v;
while(scanf("%d %d", &u, &v) && (u+v))
{
G[v].push_back(u);
in[u]++;
}
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i++)
{
if(!in[i])
{
dfs(i);
//printf("%d\n", i);
int ans = max(dp[i][0], dp[i][1]);
printf("%d\n", ans);
break;
}
}
}
return 0;
}
HDU 1520 Anniversary party / 树形DP水题！！！,布布扣,bubuko.com
HDU 1520 Anniversary party / 树形DP水题！！！
原文：http://blog.csdn.net/u011686226/article/details/22596175