剛開(kāi)始我以為是比較熟悉的樹(shù)形dp+背包，但一直wa,網(wǎng)上的代碼是非遞歸的，看到我頭暈，看了大牛的代碼后才發(fā)現(xiàn)有Trick...
       發(fā)下代碼，給有同樣問(wèn)題的人參考下

/*
    題意：給出一棵樹(shù)，每個(gè)點(diǎn)有權(quán)值，要取得這個(gè)權(quán)值需要代價(jià)，通過(guò)父親后才能到達(dá)兒子
    問(wèn)能量有限時(shí)獲得的最大值
    直接tree dp+背包
    注意的是，每個(gè)點(diǎn)至少要有一個(gè)人，即使沒(méi)有bug！
*/
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;

const int MAXN=110;
const int INF=1000000000;

int n,m;
vector<int>G[MAXN];
int bug[MAXN],brain[MAXN];
bool vi[MAXN];
int dp[MAXN][MAXN];

void dfs(int u){
    vi[u]=1;
    for(int j=1;j<=m;j++)dp[u][j]=-INF;
    dp[u][0]=0;
    int t=(bug[u]+19)/20;
    //if(!t&&brain[u])t=1; 這樣寫(xiě)會(huì)錯(cuò)
    /*
        2 1
        0 1
        0 1
        1 2
        答案是2
        上面那樣寫(xiě)答案是1
    */
    if(t<=m)dp[u][t]=brain[u];
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(vi[v])continue;
        dfs(v);
        for(int j=m;j>t;j--)
            for(int k=1;j-k>=t;k++)
                if(dp[u][j-k]!=-1&&dp[v][k]!=-1&&dp[u][j]<dp[u][j-k]+dp[v][k])
                    dp[u][j]=dp[u][j-k]+dp[v][k];
    }
    //一定要有這一句，占領(lǐng)父親取得brain，至少要有一個(gè)人！
    //雖然不用攻擊bug，所以這個(gè)人可以用來(lái)訪問(wèn)兒子
    //不需要人就能獲得brain,顯然不行
    if(dp[u][0]>0){
        dp[u][1]=max(dp[u][1],dp[u][0]);
        dp[u][0]=0;
    }
}

int main(){
    int a,b;
    while(scanf("%d%d",&n,&m),n!=-1){
        for(int i=1;i<=n;i++){
            scanf("%d%d",&bug[i],&brain[i]);
            G[i].clear();
        }
        for(int i=1;i<n;i++){
            scanf("%d%d",&a,&b);
            G[a].push_back(b);
            G[b].push_back(a);
        }
        memset(vi,0,sizeof(vi));
        dfs(1);
        int ans=0;
        for(int j=1;j<=m;j++)
            ans=max(ans,dp[1][j]);        
        printf("%d\n",ans);
    }
    return 0;
}