学步园

依赖关系形成一棵树，要选子节点必先选择其父节点

关键：把背包放在树上来做，也就是树上的01背包

#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
struct node{
int v,next;
}edge[10010];
int head[110];
int dp[110][110];
int n,m,tot;
void add(int s,int t)
{
     edge[tot].v=t;
     edge[tot].next=head[s];
     head[s]=tot++;
}
int max(int a,int b)
{
return a>b?a:b;
}
int num[110],v[110];
void dfs(int x,int f)
{
int i,j,tmp,to,k;
    tmp=(num[x]+19)/20;
for(i=head[x];i!=-1;i=edge[i].next)
    {
        to=edge[i].v;
if(to==f) continue;
        dfs(to,x);
for(j=m;j>=tmp;j--)
        {
for(k=1;j-k>=tmp&&k<=m;k++)
            {
                  dp[x][j]=max(dp[x][j],dp[x][j-k]+dp[to][k]);
            }
        }
    }
for(i=tmp;i<=m;i++) dp[x][i]+=v[x];//强制把父亲节点加进去
}
int main()
{
int i,j,a,b;
while(scanf("%d%d",&n,&m)!=EOF)
    {
if(n==-1&&m==-1) break;
        memset(head,-1,sizeof(head));
        tot=0;
for(i=1;i<=n;i++)
            scanf("%d%d",&num[i],&v[i]);
for(i=1;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            add(a,b);
            add(b,a);
        }
if(m==0)
        {
            printf("0\n");
continue;
        }
        memset(dp,0,sizeof(dp));
        dfs(1,-1);
        printf("%d\n",dp[1][m]);
    }
return 0;
}