poj 2342 Anniversary party

树形DP，其实就和求最大独立集差不多，不同的是每个结点的权值不是0和1，而是一个int。最初我还费老大心思想当权值为负时的情况，后来才明白不需要。

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int N = 6010;
 4 int fst[N],nxt[N],dp[N][2],v[N];
 5 bool root[N];
 6 int max(int a,int b)
 7 {
 8     return a>b ?a :b;
 9 }
10 void dfs(int p)
11 {
12     int e,q;
13     for(e = fst[p]; e; e = nxt[e])
14     {
15         q = v[e];
16         dfs(q);
17         dp[p][0] += max(dp[q][0],dp[q][1]);
18         dp[p][1] += dp[q][0];
19     }
20 }
21 int main()
22 {
23     int n,i,u;
24     scanf("%d",&n);
25     for(i = 1; i <= n; i++)
26         scanf("%d",&dp[i][1]);
27     for(i = 1; i < n; i++)
28     {
29         scanf("%d%d",&v[i],&u);
30         root[v[i] ] = 1;
31         nxt[i] = fst[u];
32         fst[u] = i;
33     }
34     scanf("%*d%*d");
35     for(i = 1; i <= n && root[i]; i++);
36     dfs(i);
37     printf("%d\n",max(dp[i][0],dp[i][1]));
38     return 0;
39 }