树形dp
dp[i][j]表示 i房间还有j个士兵能获得的最大价值。
当士兵数为0个的时候，就不能继续往下走了。
但当大部队遇到中途的bug为0的房间的时候，就可以不留士兵获取价值。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> tree[105];
int sum[105],val[105];
int dp[105][105];
bool vis[105];
int a,b,n,m;
void dfs(int now)
{
int need=(sum[now]+19)/20;
for(int i=need;i<=m;i++) dp[now][i]=val[now];
vis[now]=1;
for(int i=0;i<tree[now].size();i++)
{
int son=tree[now][i];
if(!vis[son])
{
vis[son]=1;
dfs(son);
for(int j=m;j>=need;j--)
{
for(int k=1;k<=j-need;k++)//至少1个人
{
dp[now][j]=max(dp[now][j],dp[now][j-k]+dp[son][k]);
}
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&m))
{
if(n==-1&&m==-1) break;
for(int i=1;i<=n;i++) scanf("%d%d",&sum[i],&val[i]),tree[i].clear();
memset(dp,0,sizeof(dp));
for(int i=1;i<n;i++)
{
scanf("%d%d",&a,&b);
tree[a].push_back(b);
tree[b].push_back(a);
}
if(!m) printf("0\n");
else
{
memset(vis,0,sizeof(vis));
dfs(1);
printf("%d\n",dp[1][m]);
}
}
return 0;
}