ZOJ 3201 树形背包问题

题目大意：

0~n-1号这n个点，每个点有个权值，由无向边形成了一棵树，希望在这棵树上找到一棵长为m的子树使总的权值最小

基本的树形背包问题

令dp[u][j] 表示u号节点对应子树中有j个节点所能得到的最大权值

dp[u][1] = val[u]

dp[u][j] = max{dp[v][k] + dp[u][j-k]} j>1  1=<k<j

我们通过dfs自底向上更新

在dfs过程中建立一个 j ，k 的循环即可

我一开始想的时候认为这个只做到了 u 的下方考虑，如果所得到的子树是要往u的上方走怎么办，想着自顶向上多一次dfs，然后就再也想不出来了- -

其实后来想想却发现如果要往上走，那么就得到的是以走到最上方的那个节点所形成的子树，那个值也已经在dp数组中保存了，不用我多去考虑了

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

const int N = 105;
int first[N] , k , val[N] , dp[N][N];

struct Edge{
    int y , next;
}e[N<<1];

void add_edge(int x , int y)
{
    e[k].y = y , e[k].next = first[x];
    first[x] = k++;
}

void  dfs(int u , int fa , int m)
{
    dp[u][1] = val[u];
    for(int i = first[u] ; i!=-1 ; i=e[i].next)
    {
        int v = e[i].y;
        if(v == fa) continue;
        dfs(v , u , m);
        for(int j = m ; j>=2 ; j--){
            for(int k=1 ; k<j ; k++)
                dp[u][j] = max(dp[u][j] , dp[v][k] + dp[u][j-k]);
        }
    }
}

int main()
{
   // freopen("a.in" , "r" , stdin);
    int n , m , x , y;
    while(scanf("%d%d" , &n , &m)==2){
        for(int i =0 ; i<n ; i++)
            scanf("%d" , val+i);

        memset(first , -1 , sizeof(first));
        k=0;
        for(int i=1 ; i<n ; i++){
            scanf("%d%d" , &x , &y);
            add_edge(x , y);
            add_edge(y , x);
        }

        memset(dp , 0 , sizeof(dp));
        dfs(0 , -1 , m);

        int maxn = 0;
        for(int i=0 ; i<n ; i++){
            maxn = max(maxn , dp[i][m]);
        }
        printf("%d
" , maxn);
    }
    return 0;
}