hdu1520 Anniversary party 樹形dp

hdu1520

比之前樹形背包要簡單多了，沒有背包的體積限制

dp[ i ] [ 0 ]  以i為根（不包括i本身）的樹上取到的最大值

dp[ i ] [ 1 ]   以i為根（包括i本身）的樹上取到的最大值

[cpp]
#include<iostream>  
#include<cstdio>  
#include<cstring>  
#include<vector>  
using namespace std; 
 
int N,V[6100]; 
vector<int>son[6010]; 
int dp[6100][2],vis[6100]; 
 
void dfs(int n){ 
    vis[n]=1; 
    int len=son[n].size(); 
    dp[n][1]=V[n]; 
    for(int i=0;i<len;i++){ 
        int k=son[n][i]; 
        if(vis[k])  continue; 
        dfs(k); 
        if(dp[n][1]<dp[n][1]+dp[k][0])   dp[n][1]=dp[n][1]+dp[k][0]; 
        dp[n][0]=max(dp[n][0],max(dp[n][0]+dp[k][1],dp[n][0]+dp[k][0])); 
    } 
} 
 
 
int main() 
{ 
    int i,j,k,u,v; 
     
    while(scanf("%d",&N)!=EOF) 
    { 
        memset(vis,0,sizeof(vis)); 
        memset(dp,0,sizeof(dp)); 
        for(i=1;i<=N;i++){ 
            scanf("%d",&V[i]); 
            son[i].clear(); 
        } 
        while(scanf("%d%d",&u,&v),u||v){ 
            son[v].push_back(u); 
            vis[u]=1;       //非根節點   
        } 
         
         
        for(i=1;i<=N;i++) 
            if(vis[i]==0){ 
                memset(vis,0,sizeof(vis)); 
            //  printf("%d\n",i);  
                 
                dfs(i);//for(j=1;j<=N;j++)   printf("%d    %d %d\n",j,dp[j][0],dp[j][1]);  
            //  printf("%d %d\n",dp[i][0],dp[i][1]);  
                printf("%d\n",max(dp[i][0],dp[i][1])); 
            } 
    } 
    return 0; 
} 
/*
7
1
-1
-1
-1
-1
-1
-1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
*/ 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;

int N,V[6100];
vector<int>son[6010];
int dp[6100][2],vis[6100];

void dfs(int n){
 vis[n]=1;
 int len=son[n].size();
 dp[n][1]=V[n];
 for(int i=0;i<len;i++){
  int k=son[n][i];
  if(vis[k]) continue;
  dfs(k);
  if(dp[n][1]<dp[n][1]+dp[k][0]) dp[n][1]=dp[n][1]+dp[k][0];
  dp[n][0]=max(dp[n][0],max(dp[n][0]+dp[k][1],dp[n][0]+dp[k][0]));
 }
}

int main()
{
 int i,j,k,u,v;
 
 while(scanf("%d",&N)!=EOF)
 {
  memset(vis,0,sizeof(vis));
  memset(dp,0,sizeof(dp));
  for(i=1;i<=N;i++){
   scanf("%d",&V[i]);
   son[i].clear();
  }
  while(scanf("%d%d",&u,&v),u||v){
   son[v].push_back(u);
   vis[u]=1;  //非根節點
  }
  
  
  for(i=1;i<=N;i++)
   if(vis[i]==0){
    memset(vis,0,sizeof(vis));
   // printf("%d\n",i);
    
    dfs(i);//for(j=1;j<=N;j++) printf("%d    %d %d\n",j,dp[j][0],dp[j][1]);
   // printf("%d %d\n",dp[i][0],dp[i][1]);
    printf("%d\n",max(dp[i][0],dp[i][1]));
   }
 }
 return 0;
}
/*
7
1
-1
-1
-1
-1
-1
-1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
*/