http://acm.hdu.edu.cn/showproblem.php?pid=1011
题意：每个节点有两个值bug和brain，当清扫该节点的所有bug时就得到brain值，只有当父节点被清空时，才可以清扫它 的子节点，而清扫需要一定的人员。给定M个人员，N个结点的树，求最大brain和
这看起来是一道非常简单的背包dp
但是
写完提交wa之后，我发现这道题，并不简单！因为他的题意并不是完全和我找到的题意一样（我承认我语文很差劲所以随便找个题解看题意。。），题目中要求每一个人是不能往回走的，所以节点bug值为0时也不能随意收集brain，一个人员只能收集一条链。当然0个人的时候不管怎么样都收集不到brain直接特判。
这个问题可以通过一个非常之骚的操作解决，操作如下
f[a][b]代表以a点为根的子树布置b个人能得到的最大brain的和
for(int k=m;k>=bu[x];k--){
for(int j=;j+k<=m;j++){//注意这个地方从1开始
f[x][k+j]=max(f[x][k+j],f[x][k]+f[y][j]);
}
}j从1开始循环完美避免了不给下面的路分配人却得到brain值的事情发生，然后就可以ac了。。。
但是并没有ac。。为什么呢。。。因为我，没有把写好的清空数据函数放到主程序里。。。
然后我wa了8次。。。引以为戒。
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=;
const double eps=1e-;
const int modn=;
int n,m;
struct nod{
int next,y;
}e[maxn*];
int bu[maxn]={},bra[maxn]={},head[maxn]={},tot=;
bool vis[maxn]={};
int f[maxn][maxn]={};
void init(int x,int y){
e[++tot].y=y;
e[tot].next=head[x];
head[x]=tot;
}
void dfs(int x){
vis[x]=;
int y;
for(int i=bu[x];i<=m;i++){
f[x][i]=bra[x];
}
for(int i=head[x];i;i=e[i].next){
y=e[i].y;
if(!vis[y]){
dfs(y);
for(int k=m;k>=bu[x];k--){
for(int j=;j+k<=m;j++){
f[x][k+j]=max(f[x][k+j],f[x][k]+f[y][j]);
}
}
}
}
}
void yu(){
tot=;memset(f,,sizeof(f));
memset(head,,sizeof(head));
memset(vis,,sizeof(vis));
}
int main(){
for(;;){
yu();
scanf("%d%d",&n,&m);
if(n==-||m==-){
break;
}
for(int i=;i<=n;i++){
scanf("%d%d",&bu[i],&bra[i]);
bu[i]=(bu[i]+)/;
}
int x,y;
for(int i=;i<n;i++){
scanf("%d%d",&x,&y);
init(x,y);init(y,x);
}
if(m==){
printf("0\n");
continue;
}
dfs();
printf("%d\n",f[][m]);
}
return ;
}