poj2486 Apple Tree （樹形dp）

題意：有一顆蘋果樹，樹上的u節點上有num[u]個蘋果，樹根為1號節點，囧king從根開始走，沒走到一個節點就把接點上的蘋果吃光，問囧king在不超過k步的情況下最多吃多少個蘋果。 

題意：有一顆蘋果樹，樹上的u節點上有num[u]個蘋果，樹根為1號節點，囧king從根開始走，沒走到一個節點就把接點上的蘋果吃光，問囧king在不超過k步的情況下最多吃多少個蘋果。解題思路：處理出兩個dp數組，f1[u][i]表示在不超過i步的情況下，從u節點開始，往下吃，吃完後回到u節點，最多能吃多少蘋果。f2[u][i]表示在不超過i步的情況下，從u節點開始往下吃，最多能吃多少蘋果。 

解題思路：處理出兩個dp數組，f1[u][i]表示在不超過i步的情況下，從u節點開始，往下吃，吃完後回到u節點，最多能吃多少蘋果。f2[u][i]表示在不超過i步的情況下，從u節點開始往下吃，最多能吃多少蘋果。

#include<stdio.h>  
#include<string.h>  
#include<algorithm>  
using namespace std ; 
 
const int maxn = 111111 ; 
 
int max ( int a , int b ) { return a > b ? a : b ; } 
int min ( int a , int b ) { return a < b ? a : b ; } 
 
struct Edge 
{ 
    int to , next ; 
} edge[maxn<<1]; 
int head[maxn] , tot , n , m ; 
int f1[111][2222]  , f2[111][222] , num[maxn] , ans , dis[1111] ; 
 
void new_edge ( int a , int b ) 
{ 
    edge[tot].to = b ; 
    edge[tot].next = head[a] ; 
    head[a] = tot ++ ; 
 
    edge[tot].to = a ; 
    edge[tot].next = head[b] ; 
    head[b] = tot ++ ; 
} 
 
int c[111][222] , d[maxn] , l ; 
 
void dfs ( int u , int fa , int *f ) 
{ 
    int i , j , k ; 
    if ( u != 1 ) 
    { 
        for ( i = dis[u] ; i <= m ; i ++ ) 
            ans = max ( ans , f2[u][m-i] + f[i] ) ; 
    } 
 
    int fuck[222] ; 
    for ( i = head[u] ; i != -1 ; i = edge[i].next ) 
    { 
        int v = edge[i].to ; 
        if ( v == fa ) continue ; 
 
        for ( j = 0 ; j <= m ; j ++ ) d[j] = 0 ; 
        int t = 0 ; 
        for ( j = head[u] ; j != -1 ; j = edge[j].next ) 
        { 
            if ( edge[j].to == v || edge[j].to == fa ) continue;  
            t ++ ; 
            for ( k = 0 ; k <= m ; k ++ ) 
                c[t][k] = f1[edge[j].to][k] ; 
        } 
        for ( j = 1 ; j <= t ; j ++ ) 
            for ( k = m ; k >= 0 ; k -- ) 
                for ( l = 0 ; l + 2 <= k ; l ++ ) 
                    d[k] = max ( d[k] , d[k-l-2] + c[j][l]  ) ; 
 
        for ( j = 0 ; j <= m ; j ++ ) fuck[j] = 0 ; 
        for ( j = dis[u] ; j < m ; j ++ ) fuck[j+1] = f[j] ; 
        for ( j = dis[u] ; j <= m ; j ++ ) 
            for ( k = 0 ; k <= m ; k ++ ) 
                if ( j + k + 1 <= m ) 
                    fuck[j+k+1] = max ( fuck[j+k+1] , f[j] + d[k] + num[u] ) ; 
        dfs ( v , u , fuck ) ; 
    } 
} 
 
void cal ( int u , int fa ) 
{ 
    int i , j , k ; 
    for ( i = head[u] ; i != -1 ; i = edge[i].next ) 
    { 
        int v = edge[i].to ; 
        if ( v == fa ) continue ; 
        dis[v] = dis[u] + 1 ; 
        cal ( v , u ) ; 
 
        for ( k = m ; k >= 0 ; k -- ) 
            for ( j = 0 ; j + 2 <= k ; j ++ ) 
                f1[u][k] = max ( f1[u][k] , f1[u][k-j-2] + f1[v][j] ) ; 
 
 
        for ( k = 1 ; k <= m ; k ++ ) f2[u][k] = max ( f2[u][k] , f2[v][k-1] ) ; 
 
 
        for ( j = 0 ; j <= m ; j ++ ) d[j] = 0 ; 
        int t = 0 ; 
        for ( j = head[u] ; j != -1 ; j = edge[j].next ) 
        { 
            if ( edge[j].to == v || edge[j].to == fa ) continue ; 
            t ++ ; 
            for ( k = 0 ; k <= m ; k ++ ) 
                c[t][k] = f1[edge[j].to][k] ; 
        } 
 
        for ( j = 1 ; j <= t ; j ++ ) 
            for ( k = m ; k >= 0 ; k -- ) 
                for ( l = 0 ; l + 2 <= k ; l ++ ) 
                    d[k] = max ( d[k] , d[k-l-2] + c[j][l]  ) ; 
 
        for ( j = 0 ; j <= m ; j ++ ) 
            for ( k = 0 ; k + 1 <= j ; k ++ ) 
                f2[u][j] = max ( f2[u][j] , f2[v][k] + d[j-k-1] ) ; 
    } 
 
    for ( i = 0 ; i <= m ; i ++ ) f1[u][i] += num[u] , f2[u][i] += num[u] ; 
    for ( i = 1 ; i <= m ; i ++ ) f1[u][i] = max ( f1[u][i] , f1[u][i-1] ) , f2[u][i] = max ( f2[u][i] , f2[u][i-1] ) ; 
} 
 
void init () 
{ 
    int i ; 
    memset ( head , -1 , sizeof ( head ) ) ; 
    memset ( f1 , 0 , sizeof ( f1 ) ) ; 
    memset ( f2 , 0 , sizeof ( f2 ) ) ; 
    memset ( dis , 0 , sizeof ( dis ) ) ; 
    tot = ans = 0 ; 
} 
 
int f[222] ; 
int main () 
{ 
    int i , j , k , a , b ; 
    while ( scanf ( "%d%d" , &n , &m ) != EOF ) 
    { 
        init () ; 
        for ( i = 1 ; i <= n ; i ++ ) scanf ( "%d" , &num[i] ) ; 
        for ( i = 1 ; i < n ; i ++ ) 
        { 
            scanf ( "%d%d" , &a , &b ) ; 
            new_edge ( a , b ) ; 
        } 
        cal ( 1 , 0 ) ; 
        ans = f2[1][m] ; 
        for ( i = 0 ; i <= m ; i ++ ) f[i] = 0 ; 
        dfs ( 1 , 0 , f ) ; 
        printf ( "%d\n" , ans ) ; 
    } 
}