【树形dp】TELE

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘;
	return x*f;
}
const int MAXN=8001;
const int INF=999999;
int N,M;
int Node[MAXN],Root[MAXN],Next[MAXN],Cost[MAXN];
int cnt;
int val[MAXN];
int tel[MAXN];
int dp[3001][3001];

void addedge(int u,int v,int w){
	++cnt;
	Node[cnt]=v; Cost[cnt]=w;
	Next[cnt]=Root[u];
	Root[u]=cnt;
	return ;
}
void dfs(int x){
	if(x>N-M){
		tel[x]=1;
		dp[x][1]=val[x];
		dp[x][0]=0;
		return ;
	}
	for(int k=Root[x];k;k=Next[k]){
		int son=Node[k];
		dfs(son);
	}
	int tmp=0;dp[x][0]=0;
	for(int k=Root[x];k;k=Next[k]){
		int son=Node[k];
		tmp+=tel[son];
		for(int t=tmp;t>=1;t--){
			for(int p=1;p<=tel[son];p++){
			    if(p>t) break;
			    dp[x][t]=max(dp[x][t],dp[son][p]+dp[x][t-p]-Cost[k]);
			}
		}
	}
	tel[x]=tmp;
	return ;
}

int main(){
	N=read(),M=read();
	for(int i=0;i<=N;i++)
	    for(int j=0;j<=M;j++) dp[i][j]=-INF;
	for(int i=1;i<=N-M;i++){
		int k=read();
		while(k--){
			int v=read(),w=read();
			addedge(i,v,w);
		}
	}
	for(int i=1;i<=M;i++) val[i+N-M]=read();
	dfs(1); int ans=M;
	while(dp[1][ans]<0) ans--;
	printf("%d\n",ans);
}