poj 2486 Apple Tree 树形dp

// 好题！mark一下，不会写！参考这里的。。。
// http://hi.baidu.com/zyz913614263/item/86f442228b3db8042a0f1c65


// 上面的链接解释很详细了，我就不再废话了>_<。
#include
  
   
#include
   
     #include
    
      #include
     
       #include
      
        using namespace std; vector
       
         tree[105]; int a[105]; int dp[2][105][205]; int n,k; int x,y; void dfs(int now,int fa=-1) { for(int i=0;i<=k;i++) dp[0][now][i]=dp[1][now][i]=a[now]; for(int i=0;i
        
         =0;i--) { for(int j=0;j<=i;j++) { dp[1][now][i+1]=max(dp[1][now][i+1],dp[0][now][i-j]+dp[1][to][j]); dp[1][now][i+2]=max(dp[1][now][i+2],dp[1][now][i-j]+dp[0][to][j]); dp[0][now][i+2]=max(dp[0][now][i+2],dp[0][now][i-j]+dp[0][to][j]); } } } } } int main() { while(~scanf("%d%d",&n,&k)) { memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) scanf("%d",&a[i]),tree[i].clear(); for(int i=1;i