换根DP学习博客
https://www.luogu.com.cn/article/wdk0q56f

树上背包

https://www.luogu.com.cn/problem/P1273

简单题意

叶子节点有权值，每条边有花费，问最多连接多少个叶子节点到根，使得权值总和大于花费总和。

做法

设 \(dp_{i,x,j}\) 为在第 x 个节点，使用前 i 个子节点的子树，选j个最大能获得的钱数。

答案就为 最大的 j 使得 \(dp_{i,x,j}\) 非负。

考虑转移

这是一个分组背包，每个子节点都是一个组，通过背包的经验，可以将 i 这一维滚动掉。
于是就没了。
注意枚举 k 时不能超过 j，也不能超过当前子节点的 size，这一细节可以优化成 \(O(N^2)\) 的复杂度。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define re register
#define PII pair<int,int>
int read()
{
	int f=1,k=0;char c = getchar();
	while(c <'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9')k=(k<<1)+(k<<3)+(c^48),c=getchar();
	return k*f;
}

const int N = 4005;

int n,m;
vector<PII> v[N];

int c[N];
//dp[i][x][j] 表示在第 x 个节点，使用前 i 个子节点的子树，选j个最大能获得的钱数。
int dp[N][N]; 
int siz[N];

void dfs(int x)
{
	if (x >= n-m+1)
	{ //判断为叶子节点
		siz[x] = 1;
		dp[x][1] = c[x]; //选一个为自己
		return;
	}
	for (int i = 0;i < v[x].size();i++) //根据分组背包，先枚举组别
	{
		auto [y,w] = v[x][i];
		dfs(y);
		siz[x] += siz[y];
		//为了滚动，倒序枚举
		for (int j = siz[x];j >= 0;j--) //前 i 个j上界为当前的size
		{
			for (int k = 0;k <= siz[y];k++) //枚举决策
			{
				if (k > j) break;
				dp[x][j] = max(dp[x][j],dp[x][j-k] + dp[y][k] - w);
			}
		}
	}
}

int main()
{
	memset(dp,-INF,sizeof dp);
	cin >> n >> m;
	for (int i = 1;i <= n-m;i++) 
	{
		int k = read();
		for (int j = 1;j <= k;j++)
		{
			int x = read(),c= read();
			v[i].push_back({x,c});	
		}
		dp[i][0] = 0; //初始化，选0个代价为0
	}
	
	for (int i = 1;i <= m;i++) c[i+n-m] = read();
	
	dfs(1);
	
	for (int k = m;k >= 0;k--)
	{
		if (dp[1][k] >= 0)
		{
			cout << k << endl;
			return 0;
		}
	}
	return 0;
}