*定义状态：
这道题是一道裸的树形背包题，设$f[i][j]$表示以$i$ 为根往下找$j$ 个叶子的最大价值，那么答案就是所有$f[1][j]≥0$当中最大的$j$。
在dp之前，我们按照后序遍历序列重新编号（即遍历到一个节点时，先搜索节点的子树，为它们编号后再为这个节点编号）。
然后开始dp，首先初始化，对$f[i][j]$赋值−$INF$，当$j==0$ 时$f[i][j]=0$ 。
*状态转移：
如果i$$点是叶子节点那么有$f[i][j]=max(f[i−1][j−1]+c[i],f[i−1][j])$ 和一般的0/1背包没什么区别
如果不是的话，如果我们取$i$的话$f[i][j]=f[i−1][j]+c[i]$，但是如果不取的话它和它的子树就一个都不能取了。
而由后序遍历定义不难推出$i$的子树节点编号在$[i−sz[i]+1,i]$之间（$sz[i]$为子树i的大小）。
所以不取的话$f[i][j]=f[i−sz[i]][j]$ ，综上$f[i][j]=max(f[i−1][j]+c[i],f[i−sz[i]][j])$
代码：
1 #include <cstdio> 2 #include <iostream> 3 #include <algorithm> 4 const int N=6000; 5 const int INF=1e9; 6 using namespace std; 7 int read(){ 8 int x = 1,a = 0; 9 char ch = getchar(); 10 while(ch < '0' || ch > '9'){ 11 if(ch == '-')x = -1; 12 ch = getchar(); 13 } 14 while(ch <= '9'&&ch >= '0'){ 15 a = a * 10 + ch - '0'; 16 ch = getchar(); 17 } 18 return x*a; 19 } 20 struct node{ 21 int to,next; 22 }ed[N]; 23 int n,m,head[N],tot; 24 void add(int u,int v){//链前 25 ed[++tot].next=head[u]; 26 ed[tot].to=v; 27 head[u]=tot; 28 } 29 int f[N][N],sz[N],idx[N],cnt,c[N]; 30 void dfs(int x){ 31 sz[x]=1; 32 for (int i = head[x];i;i=ed[i].next){ 33 int v=ed[i].to; 34 dfs(v);sz[x]+=sz[v]; //求子树大小 35 } 36 idx[++cnt]=x;//遍历顺序 37 } 38 int main(){ 39 scanf ("%d%d",&n,&m); 40 for(int i=1;i<=n-m;i++){ 41 int k=read(); 42 for(int j=1;j<=k;j++){ 43 int v=read();c[v]=-read();// 花费为负 44 add(i,v);//构建树，转播站和能转播到的节点连在一起 45 } 46 } 47 for(int i=n-m+1;i<=n;i++)c[i]+=read();// 预算为正 48 dfs(1); 49 for(int i=0;i<=cnt;i++) 50 for(int j=1;j<=m;j++) 51 f[i][j]=-INF; 52 for(int i=1;i<=cnt;i++){ 53 int u=idx[i]; 54 for(int j=1;j<=m;j++){ 55 if(n-m+1<=u)f[i][j]=max(f[i-1][j-1]+c[u],f[i-1][j]);// 是客户（叶子）节点 56 else f[i][j]=max(f[i-1][j]+c[u],f[i-sz[u]][j]); // 不是客户（叶子）节点 57 } 58 } 59 for(int i=m;i>=0;i--){ 60 if(f[cnt][i]>=0){ 61 printf("%d ",i);return 0; 62 } 63 } 64 return 0; 65 }