上树DP，记忆化搜索。
本题老师讲的方法是直接树形DP，但是由于我对树并不够了解，什么dfs也不想尝试(虽然感觉自己可以搞)，于是搞了个结构体存点以及该点的信息，用f[i][j]作为记忆化数组。以后最好能用结构体就用结构体。有条理，集中，而且对于转java有点帮助(还不知道转不转)。
代码：
1 #include <cstdio> 2 #include <algorithm> 3 #define N 6003 4 using namespace std; 5 6 struct Node{ 7 int dad,son[N],R,top; 8 }a[N]; 9 int x,y,n,root; 10 int f[N][2]; 11 int ffind(int p,int flag) 12 { 13 if(f[p][flag]) return f[p][flag]; 14 int ans=0; 15 if(flag) 16 { 17 ans=a[p].R; 18 for(int i=1;i<=a[p].top;i++) 19 { 20 ans+=ffind(a[p].son[i],0); 21 } 22 } 23 else 24 { 25 for(int i=1;i<=a[p].top;i++) 26 { 27 ans+=max(ffind(a[p].son[i],0),ffind(a[p].son[i],1)); 28 } 29 } 30 f[p][flag]=ans; 31 return ans; 32 } 33 34 int main() 35 { 36 scanf ("%d",&n); 37 for(int i=1;i<=n;i++) 38 scanf ("%d",&a[i].R); 39 for(int i=1;i<n;i++) 40 { 41 scanf ("%d%d",&x,&y); 42 a[x].dad=y; 43 a[y].son[++a[y].top]=x; 44 } 45 for(root=1;root<=n;root++) 46 { 47 if(a[root].dad==0) break; 48 } 49 50 int ans=max(ffind(root,0),ffind(root,1)); 51 /*printf("\n"); 52 for(int i=1;i<=n;i++) 53 { 54 printf("%d %d\n",ffind(i,0),ffind(i,1)); 55 }*/ 56 printf("%d",ans); 57 return 0; 58 }