f[i][j]表示i这个子树让j个 用户转播最多能赚的钱 ，
f[ i ][ j ] = max(f[ i ][ j ], f[ i ][ j - k ] f[ v ][ k ] - w[ i ] )；
最后从后往前判断到大于等于0的 f[ 1 ][ i ], i 就是最大用户数。
代码语言：javascript复制//P1273 有线电视网
//树形dp
#include <bits/stdc .h>
using namespace std;
const int maxn = 3005;
int head[maxn<<2],dp[maxn][maxn],vv[maxn];
int n,m,cnt,size[maxn],du[maxn];
struct N{
int v,nxt,w;
}ed[maxn<<2];
void add(int u,int v,int w){
cnt ;
ed[cnt].v = v;
ed[cnt].w = w;
ed[cnt].nxt = head[u];
head[u] = cnt;
}
void dfs(int u,int fa){
dp[u][0] = 0;
for(int w,v,i=head[u];i;i=ed[i].nxt){
v = ed[i].v; w = ed[i].w;
if(v==fa)continue;
dfs(v,u);
size[u] =size[v];
for(int j=size[u];j;j--){
for(int k=1;k<=min(j,size[v]);k ){
dp[u][j] = max(dp[u][j],dp[v][k] dp[u][j-k]-w);
//f[i][j]表示i这个子树让j个 用户转播最多能赚的钱
}
}
}
if(du[u]==1){
dp[u][1] = vv[u];
size[u]=1;
}
}
int main()
{
int u,w,k;
memset(dp,128,sizeof(dp));//初始化负无穷
scanf("%d %d",&n,&m);
for(int i=1;i<=n-m;i ){
scanf("%d",&k);
for(int j=1;j<=k;j ){
scanf("%d %d",&u,&w);
du[u] ; du[i] ;
add(i,u,w); add(u,i,w);
}
}
for(int i=n-m 1;i<=n;i ){
scanf("%d",&vv[i]);
}
dfs(1,0);
for(int i=m;i>=0;i--){
if(dp[1][i]>=0){
printf("%dn",i);
break;
}
}
return 0;
}
