【题意】

电视台发送信号给很多用户，每个用户有愿意出的钱，电视台经过的路线都有一定费用，求电视台不损失的情况下最多给多少用户发送信号。
【解题方法】

裸的树形DP了。

dp[i][j]代表i节点为根节点的子树j个用户的时候最大剩余费用。则dp[i][j] = max(dp[i][j], dp[i][k]+dp[son][j-k]-w[i][son]);

【AC 代码】

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 0x3f3f3f3f;
const int maxn = 3005;
int dp[maxn][maxn],head[maxn],tot;
int num[maxn],f[maxn];
struct edge{
    int to,next,w;
}E[maxn*2];
void init(){
    memset(head,-1,sizeof(head));
    tot=0;
}
void addedge(int u,int v,int w){
    E[tot].to=v,E[tot].w=w,E[tot].next=head[u],head[u]=tot++;
}
void dfs(int u,int fa)
{
    if(num[u]) f[u]=1;
    for(int i=head[u]; ~i; i=E[i].next){
        int v=E[i].to,w=E[i].w;
        if(v==fa) continue;
        dfs(v,u);
        f[u]+=f[v];
        for(int j=f[u]; j>=0; j--){
            for(int k=0; k<=j; k++){
                dp[u][j] = max(dp[u][j],dp[u][j-k]+dp[v][k]-w);
            }
        }
    }
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init();
        int k,a,b;
        for(int i=1; i<=n-m; i++){
            scanf("%d",&k);
            while(k--){
                scanf("%d%d",&a,&b);
                addedge(i,a,b);
                addedge(a,i,b);
            }
        }
        memset(num,0,sizeof(num));
        for(int i=1; i<=n; i++){
            dp[i][0]=0;
            for(int j=1; j<=m; j++){
                dp[i][j]=-inf;
            }
        }
        for(int i=n-m+1; i<=n; i++){
            scanf("%d",&num[i]);
            dp[i][1]=num[i];
        }
        int ans;
        dfs(1,-1);
        for(int j=m; j>=0; j--){
            if(dp[1][j]>=0){
                ans=j;
                break;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}