其实就是一个背包嘛，每个终端都是一个物品，体积全是1；

网上的题解很多，我copy一段

dp[i][j]表示i节点在其后代中选了j个的最大收入

dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[v][k]-w)

相信大家都看得懂这个公示，但是也许你会有所疑惑；

这个更新方程需要调用它自己！

那我怎么可以保证dp[i][j-k]中我没有包含v这个子节点的情况；

还有为什么j要倒着枚举？？？？；

其实呢，这个只不过是01背包的树版；

这相当与一维的01背包；

其实原先应该是dp[i][j][k]

表示第i个节点的前j个字节点中，我在第j个字节点选k个的最大最优情况；

把j这一个压缩掉就变成了一开始我们说的那个dp方程了；

所以呢，显然的一开始方程的j要倒着枚举，原理和一维的01背包是一样的；

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define Ll long longusing namespace std;struct cs{ int to,next,vv;}a[3001];int head[3001],v[3001],f[3001][3001];int n,m,ll,x,y,z,nn;void init(int x,int y,int z){ ll++; a[ll].to=y; a[ll].vv=z; a[ll].next=head[x]; head[x]=ll;}int dfs(int x){ //返回x节点包含了几个叶子节点 if(!head[x]){ f[x][1]=v[x];return 1; } int sum=0,son=0; for(int k=head[x];k;k=a[k].next){ son=dfs(a[k].to); sum+=son; for(int j=sum;j;j--) for(int i=1;i<=min(son,j);i++) f[x][j]=max(f[x][j],f[x][j-i]+f[a[k].to][i]-a[k].vv); } return sum;}int main(){ memset(f,-63,sizeof f); scanf("%d%d",&n,&m); for(int i=1;i<=n-m;i++){ scanf("%d",&z);nn++; for(int i=1;i<=z;i++){ scanf("%d%d",&x,&y); init(nn,x,y); } } for(int i=1;i<=m;i++)scanf("%d",&v[++nn]); for(int i=0;i<=n;i++)f[i][0]=0; nn=dfs(1); for(int i=m;i>=0;i--) if(f[1][i]>=0){ printf("%d",i);return 0; }}