题目是说给一棵树，叶子结点有负权，边有正权，问最多能选多少个叶子结点，使从叶子到根的权值和小于等于0。
考虑数据规模表示出状态：dp[u][k]表示在u结点为根的子树中选择k个叶子结点的最小权值
最后就从d[1][k]中找满足的最大的k。不过单这样转移时间复杂度是指数级，显然这题就是用树上背包了。
不过其实这题时间复杂度不会算= =反正感觉挺靠谱，交了就AC了。。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF (1<<29)
#define MAXN 3001
struct Edge{
int u,v,w,next;
}edge[MAXN];
int NE,head[MAXN];
void addEdge(int u,int v,int w){
edge[NE].u=u; edge[NE].v=v; edge[NE].w=w;
edge[NE].next=head[u]; head[u]=NE++;
} int d[MAXN][MAXN],size[MAXN];
void dfs(int u){
bool isleaf=;
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
dfs(v);
size[u]+=size[v];
isleaf=;
}
if(isleaf) size[u]=;
}
int val[MAXN];
void dp(int u){
bool isleaf=;
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
dp(v);
isleaf=;
for(int j=size[u]; j>=; --j){
for(int k=; k<=min(j,size[v]); ++k) d[u][j]=min(d[u][j],d[u][j-k]+d[v][k]+edge[i].w);
}
}
if(isleaf) d[u][]=-val[u];
}
int main(){
memset(head,-,sizeof(head));
int n,m,k,a,b;
scanf("%d%d",&n,&m);
for(int i=; i<=n; ++i){
for(int j=; j<=m; ++j) d[i][j]=INF;
}
for(int i=; i<=n-m; ++i){
scanf("%d",&k);
while(k--){
scanf("%d%d",&a,&b);
addEdge(i,a,b);
}
}
for(int i=n-m+; i<=n; ++i){
scanf("%d",val+i);
}
dfs();
dp();
for(int i=m; i>=; --i){
if(d[][i]<=){
printf("%d",i);
break;
}
}
return ;
}