题意：略。
思路：用dp[i][k]来表示结点i给k个用户提供节目时的最大盈利（可能为负）。
则递推方程为: dp[i][j] = max(dp[i][j], dp[i][m] + dp[v][j-m] - cost)
其中v为i的孩子，cost为i向v提供节目的花费。
另外注意代码里dp过程的这几行
1 for (int j = num[x]; j >= 0; j--) 2 for (int k = 1; k <= num[v]; k++) 3 dp[x][j+k] = max(dp[x][j+k], dp[x][j] + dp[v][k] - edge[i].w);
假设当前正考虑的孩子结点是v，则孩子1...(v-1)覆盖的用户数量为num[x]，即i已经考虑过的用户数量。在这里枚举时需要从大到小枚举，不然可能j=1的情况会影响到j=2的情况。另一种处理方法就是，将结点i所有的dp[i][j]值每次都先用tem[j]另存起来，dp时直接用tem[j]，这样就不需要考虑枚举的顺序了。
1 #include<stdio.h> 2 #include<string.h> 3 #include<algorithm> 4 #define maxn 3005 5 #define inf 0x3f3f3f3f 6 using namespace std; 7 struct node 8 { 9 int v, w, next; 10 }edge[maxn]; 11 int num_edge, head[maxn]; 12 void init_edge() 13 { 14 num_edge = 0; 15 memset(head, -1, sizeof(head)); 16 } 17 void addedge(int a,int b,int c) 18 { 19 edge[num_edge].v = b; 20 edge[num_edge].w = c; 21 edge[num_edge].next = head[a]; 22 head[a] = num_edge++; 23 } 24 25 int n, m, num[maxn], dp[maxn][maxn]; 26 void dfs(int x) 27 { 28 for (int i = head[x]; i != -1; i = edge[i].next) 29 { 30 int v = edge[i].v; 31 dfs(v); 32 for (int j = num[x]; j >= 0; j--) 33 for (int k = 1; k <= num[v]; k++) 34 dp[x][j+k] = max(dp[x][j+k], dp[x][j] + dp[v][k] - edge[i].w); 35 num[x] += num[v];//x结点已经考虑过的用户数 36 } 37 } 38 int main() 39 { 40 //freopen("data.in", "r", stdin); 41 scanf("%d%d", &n, &m); 42 init_edge(); 43 for (int i = 1; i <= n - m; i++) 44 { 45 num[i] = 0;//i已经考虑过的用户数量为0 46 int k; 47 scanf("%d", &k); 48 while (k--) 49 { 50 int b, c; 51 scanf("%d%d", &b, &c); 52 addedge(i, b, c); 53 } 54 } 55 for (int i = 1; i <= n; i++) 56 for (int j = 1; j <= m; j++) 57 dp[i][j] = -inf; 58 for (int i = n - m + 1; i <= n; i++) 59 { 60 num[i] = 1; 61 scanf("%d", &dp[i][1]); 62 } 63 dfs(1); 64 for (int i = m; i >= 0; i--) if (dp[1][i] >= 0) 65 { 66 printf("%d ", i); 67 break; 68 } 69 return 0; 70 }