题意：有n个房间，有n-1条道路连接着n个房间，每个房间都有若干个野怪和一定的能量值，有m个士兵从1房间入口进去，到达每个房间必须要留下若干士兵杀死所有的野怪，然后其他人继续走，（一个士兵可以杀死20只 野怪）问可以获得的最大能量值是多少？
分析:要想进入一个房间，必须把前面所有进过的房间的野怪都杀死，当某个房间的野怪数量是0的时候也需要至少派出一个人来进入这个房间来获得能量。
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"algorithm"
#include"math.h"
#define M 222
#define inf 0x3f3f3f3f
#define eps 1e-10
using namespace std;
struct node
{int u,v,next;
}edge[M*2];
int t,head[M],dp[M][M],m,bug[M],value[M],num[M];
void init()
{t=0;memset(head,-1,sizeof(head));
}
void add(int u,int v)
{edge[t].u=u;edge[t].v=v;edge[t].next=head[u];head[u]=t++;
}
void dfs(int u,int f,int cost)
{num[u]=(bug[u]+19)/20;for(int i=num[u];i<=cost;i++)//当到达当前u节点的时候最多还余下cost士兵dp[u][i]=value[u];//把该节点至少需要的士兵到最大的士兵全部赋值for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(v==f)continue;dfs(v,u,cost-num[u]);//到达下一间房间还有的士兵数目for(int j=cost;j>=num[u];j--){for(int k=1;k<=j;k++){if(k>=num[v]&&j-k>=num[u])//动态枚举状态搜索最大值dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);}}}
}
int main()
{int n,i,a,b;while(scanf("%d%d",&n,&m),n!=-1||m!=-1){for(i=1;i<=n;i++)scanf("%d%d",&bug[i],&value[i]);init();for(i=1;i<n;i++){scanf("%d%d",&a,&b);add(a,b);add(b,a);}memset(dp,0,sizeof(dp));if(m==0){printf("0\n");continue;}dfs(1,1,m);printf("%d\n",dp[1][m]);}}
