做过树上背包的同学应该会觉得这题比较简单，不过如果是没有做过的同学的话可能就...（~~比如我~~）
首先给大家推荐一道树上背包入门题：poj2486 以及讲解：qwq
那么这道题怎么做呢？
我一开始想的是先贪心处理收入大于花费的子树，然后用f[i][j]表示编号为i的节点所代表的子树在花费为j时能够开通的最多的用户数目。然后发现第二维不知道范围，连数组开多大都不知道=-=
所以我们只好换一种思路，设f[i][j]表示编号为i的节点所代表的子树在开通j个用户时的最大利润（即用户缴费-传输花费）。那么转移方程就是f[i][j] = max{f[v][k]+f[i][j-k]-e[i].val} （特殊地，当j为0时函数值为0；叶子节点x的f[x][1]=w[x]） （v表示i的子节点，val为开通一条边的花费，w[i]为i用户缴费数额）
一个小优化（60->AC）就是算出每个子节点的用户数，这样就不用每次j都从m开始枚举了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define LL long long 7 #define RI register int 8 using namespace std; 9 const int INF = 0x7ffffff ; 10 const int N = 3000 + 10 ; 11 12 inline int read() { 13 int k = 0 , f = 1 ; char c = getchar() ; 14 for( ; !isdigit(c) ; c = getchar()) 15 if(c == '-') f = -1 ; 16 for( ; isdigit(c) ; c = getchar()) 17 k = k*10 + c-'0' ; 18 return k*f ; 19 } 20 struct Edge { 21 int to, next, val ; 22 }e[N<<1] ; 23 int n, m ; int head[N], f[N][N], w[N] ; // f记录最大利润 24 inline void add_edge(int x,int y,int z) { 25 static int cnt = 0 ; 26 e[++cnt].to = y, e[cnt].next = head[x], head[x] = cnt, e[cnt].val = z ; 27 } 28 29 int dfs(int x,int fa) { 30 f[x][0] = 0 ; 31 if(x > n-m) { 32 f[x][1] = w[x] ; return 1 ; 33 } 34 int tot = 0 ; 35 for(int i=head[x];i;i=e[i].next) { 36 int y = e[i].to ; if(y == fa) continue ; 37 tot += dfs(y,x) ; 38 for(int j=tot;j;j--) { // 从m开始会T哦qwq 39 for(int k=0;k<=j;k++) { 40 f[x][j] = max(f[x][j],f[y][k]+f[x][j-k]-e[i].val) ; 41 } 42 } 43 } 44 return tot ; 45 } 46 47 int main() { 48 n = read(), m = read() ; 49 int mm = n-m ; 50 for(int i=1;i<=mm;i++) { 51 int k = read() ; 52 for(int j=1;j<=k;j++) { 53 int x = read(), z = read() ; 54 add_edge(i,x,z) ; add_edge(x,i,z) ; 55 } 56 } 57 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j] = -INF ; 58 for(int i=n-m+1;i<=n;i++) w[i] = read() ; 59 dfs(1,0) ; 60 for(int i=m;i>=0;i--) { 61 if(f[1][i] >= 0) { 62 printf("%d",i) ; return 0 ; 63 } 64 } 65 }