HDU 4616 Game 树形DP

题意：有棵树上有n个结点，每个点有若干价值的礼物，有些点可能有馅阱，有m次掉入馅阱的机会，但

第m次掉入馅阱后则不能再走，并每个点最多只能经过一次。问：可以任意点为起点，最多可以拿

到总价值多大的礼物。

分析：

分两种情况：

Ⅰ、以馅点做为起始点

Ⅱ、以非馅阱点做为起始点

代码：

一、从下往上搜（自己写的代码）

#include  
#include  
#include  
#include  
using namespace std; 
typedef long long LL; 
const int maxn=55555; 
vectorTree[maxn]; 
LL val[maxn],dp[2][maxn][5],ans; 
int vid[maxn],par[maxn]; 
int n,m; 
LL max(LL a,LL b){ 
    return a>b a:b; 
} 
void DFS(int cnt){ 
    int len=Tree[cnt].size(),q=0; 
    for(int i=0;i
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn=55555;
vectorTree[maxn];
LL val[maxn],dp[2][maxn][5],ans;
int vid[maxn],par[maxn];
int n,m;
LL max(LL a,LL b){
    return a>b a:b;
}
void DFS(int cnt){
    int len=Tree[cnt].size(),q=0;
    for(int i=0;i 
 

 二、从上往下搜（参考神牛代码写的）
 
 

  
 
 
#include  
#include  
#include  
#include  
using namespace std; 
const int maxn=55555; 
int n,m; 
int val[maxn],vid[maxn]; 
int up[2][maxn][4]; 
int dp[2][maxn][4]; 
vectorG[maxn]; 
void DFS(int cnt,int fa){ 
    up[0][cnt][0]=dp[0][cnt][0]=val[cnt]; 
    if(val[cnt]) up[1][cnt][1]=dp[1][cnt][1]=val[cnt]; 
    if(fa!=-1){ 
        for(int i=0;i<=m;++i){ 
            if(i!=m&&(up[0][fa][i]||dp[0][fa][i])) 
                dp[0][cnt][i+vid[cnt]]=max(dp[0][fa][i],up[0][fa][i])+val[cnt]; 
            if(i==m&&vid[cnt]) continue; 
            if(dp[1][fa][i]||up[1][fa][i]) 
                dp[1][cnt][i+vid[cnt]]=max(dp[1][fa][i],up[1][fa][i])+val[cnt]; 
        } 
    } 
    int len=G[cnt].size(); 
    for(int i=0;i
#include
#include
#include
using namespace std;
const int maxn=55555;
int n,m;
int val[maxn],vid[maxn];
int up[2][maxn][4];
int dp[2][maxn][4];
vectorG[maxn];
void DFS(int cnt,int fa){
    up[0][cnt][0]=dp[0][cnt][0]=val[cnt];
    if(val[cnt]) up[1][cnt][1]=dp[1][cnt][1]=val[cnt];
    if(fa!=-1){
        for(int i=0;i<=m;++i){
            if(i!=m&&(up[0][fa][i]||dp[0][fa][i]))
                dp[0][cnt][i+vid[cnt]]=max(dp[0][fa][i],up[0][fa][i])+val[cnt];
            if(i==m&&vid[cnt]) continue;
            if(dp[1][fa][i]||up[1][fa][i])
                dp[1][cnt][i+vid[cnt]]=max(dp[1][fa][i],up[1][fa][i])+val[cnt];
        }
    }
    int len=G[cnt].size();
    for(int i=0;i