一道树形背包。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
using namespace std;
const int N=6e3+5;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;
    while(c<'0'||c>'9')c=gc;
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
}
void qw(int x)
{
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
struct edge{int y,next,d;}a[N<<1];int len,last[N];
void ins(int x,int y,int d){a[++len]=(edge){y,last[x],d};last[x]=len;}
int f[N][3005],c[N];int n,m;
void dfs(int x,int fa)
{
    c[x]=1;
    for(int k=last[x],y;k;k=a[k].next)
    {
        y=a[k].y;if(y==fa)continue;
        dfs(y,x);
        c[x]+=c[y];
        for(int i=min(c[x],m);i;i--)
        {
            int mn=min(i,c[y]);
            for(int j=mn;j;j--)
                f[x][i]=max(f[x][i],f[x][i-j]+f[y][j]+a[k].d);
        }
    }
}
int main()
{
    qr(n),qr(m);
    for(int i=1;i<=n-m;i++)
    {
        int k;qr(k);
        for(int j=1,y,d;j<=k;j++)
            qr(y),qr(d),ins(i,y,-d);
    }
    memset(f,0xcf,sizeof(f));
    for(int i=1;i<=n-m;i++)f[i][0]=0;
    for(int i=n-m+1;i<=n;i++)
        qr(f[i][1]),f[i][0]=0;
    dfs(1,0);
    for(int i=m;i>=0;i--)if(f[1][i]>=0){printf("%d\n",i);return 0;}
    return 0;
}