Link:

Solution:

比较裸的树形$dp$

令$dp[i][j]$表示以$i$为根的子树中选$j$个叶子的最小代价

最后找到使得$dp[1][k]\ge 0$的最大$k$即可

Code:

#include 
     
      using namespace std;const int MAXN=3005;struct edge{
   int nxt,to;}e[MAXN<<2];int n,m,x,y,w[MAXN],sz[MAXN],dp[MAXN][MAXN],head[MAXN],tot;void add_edge(int from,int to){    e[++tot].nxt=head[from];e[tot].to=to;head[from]=tot;    e[++tot].nxt=head[to];e[tot].to=from;head[to]=tot;}void dfs(int x,int anc){    dp[x][0]=0;    for(int i=head[x];i;i=e[i].nxt)    {        if(e[i].to==anc) continue;        dfs(e[i].to,x);sz[x]+=sz[e[i].to];        for(int j=sz[x];j>=1;j--)            for(int k=1;k<=j;k++)                dp[x][j]=max(dp[x][j],dp[e[i].to][k]+dp[x][j-k]-w[e[i].to]);    }}int main(){    memset(dp,0x80,sizeof(dp));    scanf("%d%d",&n,&m);    for(int i=1;i<=n-m;i++)    {        int cnt;scanf("%d",&cnt);        for(int j=1;j<=cnt;j++)            scanf("%d%d",&x,&y),add_edge(i,x),w[x]=y;    }    for(int i=n-m+1;i<=n;i++)        scanf("%d",&dp[i][1]),sz[i]=1;    dfs(1,0);    for(int i=m;i>=1;i--)        if(dp[1][i]>=0){printf("%d",i);break;}    return 0;}