hdu1520 树形DP

 1 /*
 2  * 树形DP
 3  */
 4 #include<cstdio>
 5 #include<cstring>
 6 #include<vector>
 7 using namespace std;
 8 #define Max(x,y) (x>y?x:y)
 9 #define max 6000+10
10 
11 //dp[i][0],dp[i][1],当前节点为i,在父亲去或没去的情况下的最大值
12 vector<int> adj[max];
13 int d[max][2],a[max],n;
14 bool vis[max][2],in[max];
15 
16 int dp(int i,int j){
17     if(vis[i][j]){
18         return d[i][j];
19     }
20     vis[i][j]=true;
21     int& ans=d[i][j];
22 
23     if(!j){//i的父亲没去那么i可以去
24       ans=a[i];
25       for(int k=0;k<adj[i].size();k++){
26             ans+=dp(adj[i][k],1);
27       }
28     }
29 
30     int sum=0;//任何人都可以选择不去
31     for(int k=0;k<adj[i].size();k++){
32         sum+=dp(adj[i][k],0);
33     }
34     ans=Max(ans,sum);
35     return ans;
36 }
37 
38 int main(){
39     while(~scanf("%d",&n)){
40         memset(vis,false,sizeof(vis));
41         memset(in,false,sizeof(in));
42         memset(d,0,sizeof(d));
43         for(int i=1;i<=n;i++){
44             scanf("%d",&a[i]);
45             adj[i].clear();
46         }
47         int a,b;
48         while(scanf("%d%d",&a,&b)&&a&&b){
49             adj[b].push_back(a); in[a]=true;
50         }
51         int root;//找到校长，树根
52         for(int i=1;i<=n;i++){
53             if(!in[i]){
54                 root=i;break;
55             }
56         }
57         int ans=dp(root,0);
58         printf("%d
",ans);
59     }
60 }