题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1011
题意：有N个房间，房间的连通性为树形的，就是说你要占领子结点，必须要先占领 父结点，每个房间有第一定的价值，每个房间里面有敌人，每个士兵能消灭20个敌人，现在给你m个士兵，问你能获得的最大价值为多少。
题解：dp[i][j]表示用j个士兵占领以i为根的树的最大价值，然后DFS搜树。注意：当m等于0时直接输出0，房间内没敌人也要放一个士兵。
#include<cstdio>
#define FFC(i,a,b) for(int i=a;i<=b;i++)
#define max(a,b) ((a)>(b)?(a):(b))
const int maxn=;
int n,m,ik,g[maxn],nxt[*maxn],v[*maxn],ed,xx,yy,tx,dp[maxn][maxn];
void adg(int x,int y){v[++ed]=y,nxt[ed]=g[x],g[x]=ed;}
struct node{int x,c;}nd[maxn];
void fuck(int now,int pre){
FFC(i,nd[now].x,m)dp[now][i]=nd[now].c;
for(int i=g[now];i;i=nxt[i]){
int son=v[i];
if(son==pre)continue;
fuck(son,now);
for(int j=m;j>=nd[now].x;j--)
for(int k=;k<=j-nd[now].x;k++)
dp[now][j]=max(dp[now][j],dp[now][j-k]+dp[son][k]);
}
}
int main(){
while(~scanf("%d%d",&n,&m),n!=-){
for(ik=ed=;ik<=n;ik++)g[ik]=;
FFC(i,,n)scanf("%d%d",&tx,&nd[i].c),nd[i].x=(tx+)/;
FFC(i,,n-)scanf("%d%d",&xx,&yy),adg(xx,yy),adg(yy,xx);
if(m==){printf("0\n");continue;}
FFC(i,,n)FFC(j,,m)dp[i][j]=;
fuck(,);
printf("%d\n",dp[][m]);
}
return ;
}