一开始我写的普通的树形dp，但是只有10分……（泪流成河）
讲一讲后来想到的正解：
由于问最多选多少，又要满足最优解下传，那么我们自然规定 f [ i ] [ j ] 为以 i 为根的子树中，选取 j 个点所能获得的最大利润，当然这些点不包括中转站。
那么最后我们从 n 往前看一遍，如果存在 f [ 1 ] [ i ] 大于等于0，那么就满足不亏本，直接输出就可以了
那，在一个节点，我们就不仅仅是看它的子节点而应该看它的子节点所在的子树，也就是说我们会看 f [ v ] [ i ~ size [ v ] ] ，来更新 u 。那么就要用到分组背包，在枚举边的时候就是在枚举组数，枚举 u 的节点个数就是在枚举背包容量，在枚举子树的取点情况就是在枚举每一组的具体情况。
对于一开始我写的树形dp为什么不对，存在一个致命的错误！我之前的思路是每一次如果当前子树会至少不亏本，就ans下传，并且更新当前节点。但是事实上不需要每一次转移都不亏本，这次的亏本可以靠下一次的盈利赚回来，所以我们必须记录所有状态，最后找最优的！那么只能用树上分组dp，单单普通树dp是不行的。
下面是代码：
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; #define maxn 3000 struct node { int to,nxt,cost; } edge[10000010]; int f[maxn][maxn],val[maxn],head[maxn]; int cnt,n,m; void add(int a,int b,int c) { edge[++cnt].to=b; edge[cnt].nxt=head[a]; head[a]=cnt; edge[cnt].cost=c; } int dp(int u,int fa) { if (u>=n-m+1) { f[u][1]=val[u]; return 1; } int tot=0; for(int i=head[u]; i; i=edge[i].nxt) { int v=edge[i].to; if(v==fa) continue; int son=dp(v,u); tot+=son; for(int j=tot; j>=0; j--) for(int k=0; k<=son; k++) if(k<=j) f[u][j]=max(f[u][j-k]+f[v][k]-edge[i].cost,f[u][j]); } return tot; } int main() { memset(f,~0x3f,sizeof(f)); scanf("%d%d",&n,&m); for(int i=1; i<=n-m; i++) { int k; scanf("%d",&k); for(int j=1; j<=k; j++) { int x,c; scanf("%d%d",&x,&c); add(i,x,c); add(x,i,c); } } for(int i=n-m+1; i<=n; i++) scanf("%d",&val[i]); for(int i=1; i<=n; i++) f[i][0]=0; dp(1,0); for(int i=n; i>=0; i--) if(f[1][i]>=0) { printf("%d",i); return 0; } printf("0"); return 0; }