我用的是多叉树转二叉树的方法，这题只要分四种情况考虑就行了：
① 这是用户节点，且没有兄弟（右儿子）；
② 这是一个用户节点，但有右子（兄弟节点）；
③ 这是转播站，且没有兄弟节点；
④ 这是个转播站，且有兄弟节点。
详细过程可以看代码，里面有很详细的注释：
#include <cstdio>
struct tree {
int lc,rc; //多叉树转二叉树：左儿子右兄弟
int val; //选择选择节点i时能赚多少钱（该节点的值（如果是中转站则为0）-父节点连到这个节点的边的值）
int num; //表示该节点为根的树，最多有多少个用户节点
};
const int maxn=;
int n,m;
tree a[maxn+];
int dp[maxn+][maxn+];
int maximum(int x, int y) {
if (x>y) return x;
return y;
}
//计算以x为根的树最多有多少个用户节点
int count(int x) {
int res=;
//如果自己是用户节点，答案+1
if (a[x].lc==)
res++;
//如果有左右子，则递归统计
if (a[x].rc!=)
res+=count(a[x].rc);
if (a[x].lc!=)
res+=count(a[x].lc);
a[x].num=res;
return res;
}
void init() {
scanf("%d%d",&n,&m);
//第i个转播站的信息
for (int i=; i<=n-m; i++) {
int ii,k,vv;
scanf("%d",&k);
//对k=1的特殊处理，要放在这个转播站的左儿子上
scanf("%d%d",&ii,&vv);
a[i].lc=ii;
a[ii].val-=vv;
//其余的放在之前处理过的兄弟节点的右儿子上
for (int j=; j<=k; j++) {
int x,v;
scanf("%d%d",&x,&v);
a[ii].rc=x;
a[x].val-=v;
ii=x;
}
}
//用户节点的数据
for (int i=n-m+; i<=n; i++) {
int x;
scanf("%d",&x);
a[i].val+=x;
}
//计算结构体中的num的值，搜索时有用
count();
}
//dp[root][x]表示以root为根的树，里面有x个用户节点，所能赚到的最多的钱数
int dfs(int root, int x) {
if (dp[root][x]!=) return dp[root][x]; //记忆化搜索
if (x==) return ; //如果没有连任何一个用户节点，则不赚不亏，返回0
//如果这是用户节点，且没有兄弟（右儿子），那么就加上这个节点的值
if (a[root].lc==&&a[root].rc==)
return dp[root][x]=a[root].val;
//如果这是转播站且没有兄弟节点，那么只能往左子（儿子节点）走
//因为经过这个节点，所以要加上这个答案。再递归左子树。
if (a[root].lc!=&&a[root].rc==)
return dp[root][x]=dfs(a[root].lc,x)+a[root].val;
//如果是一个用户节点，但有右子（兄弟节点）
//那么分选与不选两种情况考虑
if (a[root].lc==&&a[root].rc!=) {
//选的话要加上它的值
int res=dfs(a[root].rc,x-)+a[root].val;
//不选的话有限制条件：现在要保留的用户节点数(x)不大于它右子树里的用户节点数
//即保证它的右子里至少有x个用户节点
if (a[a[root].rc].num>=x)
res=maximum(res,dfs(a[root].rc,x)); //取两种情况中的较优情况
return dp[root][x]=res;
}
//否则这是个转播站，且有兄弟节点
int res=-0x7F7F7F7F;
//枚举在分给左子树i个用户节点，右子树x-i个用户节点的可能性，取最优
//特别注意：当不传给这个中转站，只给它的兄弟节点（右子）时，可以不取这个节点的值！
//故i从1开始，而非0（我因为这个WA了好多次）
for (int i=; i<=x; i++) {
if (a[a[root].lc].num<i) continue; //如果左子树里只有不到i个用户节点，不满足条件
if (a[a[root].rc].num<x-i) continue; //右子同理
res=maximum(res,dfs(a[root].lc,i)+dfs(a[root].rc,x-i)+a[root].val);
}
//如果全给其兄弟节点时兄弟节点里可以有这么多用户节点(num>=x)，则取较优值
if (a[a[root].rc].num>=x)
res=maximum(res,dfs(a[root].rc,x));
return dp[root][x]=res;
}
int main() {
init();
for (int i=m; i>=; i--) { //从m~0逆序枚举给i个用户信号的情况
int ans=dfs(,i); //从根节点(1)开始记忆化搜索
//如果不会亏本，则跳出循环，直接输出答案
if (ans>=) {
printf("%d\n",i);
break;
}
}
return ;
}