hdu 1011 Starship Troopers

需要注意的是   m==0时   特判输出0；

总的来说。。简单的树形dp

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
#include <vector>
using namespace std;

const int maxn = 101;
const int inf = 0x3f3f3f3f;
int dp[maxn][maxn];
struct pp
{
    int r,c;
}num[maxn];
int vis[maxn];
int n,m;
vector<int >vv[maxn];
void DP(int u)
{
    for(int i=num[u].r;i<=m;i++)
    dp[u][i]=num[u].c;
    vis[u]=1;
    for(int i=0;i<vv[u].size();i++)
    {
        int v=vv[u][i];
        if(vis[v]) continue;
        DP(v);
        for(int k=m;k>=num[u].r;k--)
        {
            for(int j=1;j<=k&&k-j>=num[u].r;j++)
                dp[u][k]=max(dp[u][k],dp[v][j]+dp[u][k-j]);
        }
    }

}
int main()
{
    while(~scanf("%d%d",&n,&m)&&(n!=-1&&m!=-1))
    {
        for(int i=0;i<=n;i++) vv[i].clear();
        memset(dp,0,sizeof(dp));
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)
        {
            int u,v;
            scanf("%d%d",&u,&num[i].c);
            u=(u+19)/20;
            num[i].r=u;
        }
        for(int i=1;i<n;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            vv[u].push_back(v);
            vv[v].push_back(u);
        }
        DP(1);
        if(!m) puts("0");
        else 
        printf("%d\n",dp[1][m]);
    }
    return 0;
}