題意：
一棵結(jié)點帶權(quán)樹，大小(結(jié)點數(shù))為k的子樹的權(quán)值和最大為多少。

初步分析
這道題其實就是一道01背包問題只是是在樹上做而已。背包的總?cè)萘烤褪莐個結(jié)點（一定得剛好裝滿），每個物品的價值就是結(jié)點的權(quán)值w[i].注意，并不是隨便選取結(jié)點就行了。而是一定得是子樹。那么這一點我們要怎么實現(xiàn)呢。首先我們用dp[i][j]來表示以結(jié)點i為首的結(jié)點數(shù)為j的權(quán)值最大的一棵子樹。那么dp[i][j]的狀態(tài)方程怎么寫呢？dp[i][j]=max(dp[i][j],dp[i][j-w] dp[v][w])(v是結(jié)點i的子節(jié)點，1=<j<=cnt[i],0<w<j)注意我們是怎么保證dp[i][j]表示的是以結(jié)點i為首的子樹呢？新節(jié)點所能取得的最大結(jié)點數(shù)只能是j-1,因為dp[i][1]始終代表的是結(jié)點i，所以才能保證都是以結(jié)點i為首的子樹。而且由于是01背包所以我們的背包容量j從大到小更新，這樣保證所有的小值都是上一次子節(jié)點的更新值而不是重復使用當前結(jié)點的值(不然的話就變成完全背包了)。

直接上代碼

#include <iostream>
#include <string.h>
using  namespace std;
const int MAX_N=110;
const int MAX_M=220;
int w[MAX_N];
int dp[MAX_N][MAX_N];
int cnt[MAX_N];
int n,k,answer=0;

//我們這里用圖來儲存樹，在遍歷的時候通過一個father參數(shù)就可以轉(zhuǎn)化為樹了。沒有必要用一個father數(shù)組來儲存
int ans=0;
int head[MAX_N];
struct edge{
    int v;
    int next;
}eid[MAX_M];

void insert(int u,int v){
    eid[ans].v=v;
    eid[ans].next=head[u];
    head[u]=ans  ;
}

int read(){
    int w=1,s=0;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-'){
           w*=-1;
        }
        ch=getchar();
    }
    while(isdigit(ch)){
        s=(s<<1) (s<<3) ch-48;
        ch=getchar();
    }
    return s*w;
}
int dfs(int node,int father){
    cnt[node]=1;
    for(int i=head[node];i!=-1;i=eid[i].next){
        int v=eid[i].v;
        if(v==father) continue;
        cnt[node] =dfs(v,node);
    }
    dp[node][1]=w[node];

    for(int i=head[node];i!=-1;i=eid[i].next){
        int v=eid[i].v;
        if(v==father) continue;
        for(int j=cnt[node];j>=1;--j) {
            for (int m = 0; m <=cnt[v] && m<j ;   m) {
                dp[node][j] = max(dp[node][j], dp[node][j - m] dp[v][m]);
            }
        }
    }

    answer=max(answer,dp[node][k]);

    return cnt[node];
}

int main() {

    while(scanf("%d %d",&n,&k)!=EOF) {

        for (int i = 1; i <= n;   i) {
            w[i] = read();
        }
        memset(head, -1, sizeof(head));
        ans=0;
        for (int i = 0; i <MAX_N;   i) {
            for (int j = 0; j <MAX_N;   j) {
                dp[i][j] = 0;
            }
        }

        for (int i = 1; i <= n - 1;   i) {
            int x, y;
            x = read() 1;
            y = read() 1;

            insert(x, y);
            insert(y, x);
        }

        dfs(1, -1);
        cout <<answer<<endl;
        answer=0;
    }
    return 0;
}