学步园

解题方法

树状DP

dp[i][j] -> 表示以 i 结点为根去到 j 个叶子结点的路径权值和加起来最大是多少

那么用子结点 v 去优化父结点 u 的转移方程如下

dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k] - W[u][v]); 其中 (1<=j<=子树u拥有的叶子结点数) (1<=k<=子树v拥有的叶子结点数) 

即像01背包那样用以子结点为根的子树的一部分去更新父结点 这里要考虑重复使用一部分去更新的情况 详细见代码

参考代码 - 有疑问的地方在下方留言 看到会尽快回复的

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

const int INF = 1<<29;

int dp[3010][3010];
int num[3010];
vector<int>M[3010];
vector<int>W[3010];
int in[3010], n, m;
int tmp[3010];

void DFS(int u, int fa) {
	if(u > n-m) { // 如果结点 u 是叶子结点的话 直接把与u相连的边的权值赋给 dp[u][1] 
		dp[u][1] = in[u];
		return ;
	}
	for( int i=0; i<M[u].size(); i++ ) { // 枚举 u 的子结点
		int v = M[u][i];
		if(v == fa) continue;
		DFS(v, u);
		for( int j=1; j<=num[u]; j++ ) tmp[j] = dp[u][j]; // 先保存结点 u 的数据 避免某一部分重复更新
		for( int j=1; j<=num[v]; j++ ) { // 相当于01背包中的 num[v]件物品 每件物品的体积是 j 价值是 dp[v][j]
			for( int k=num[u]; k>=j; k-- ) {
				dp[u][k] = max(dp[u][k], tmp[k-j]+dp[v][j] - W[u][i]); // 如果不使用 tmp数组的话 子结点v的某一比较优的部分会重复使用
			}	
		}
	}
}

void Init(int u, int fa) { // 求以 u 为根的子树包含的叶子结点数
	if(u > n-m) {
		num[u] = 1;
		return ;
	}
	num[u] = 0;
	for( int i=0; i<M[u].size(); i++ ) {
		int v = M[u][i];
		if(v == fa) continue;
		Init(v, u);
		num[u] += num[v];
	}
}

int main() {
	freopen("in", "r", stdin);
	while(scanf("%d%d", &n, &m) != EOF) {
		for( int i=1; i<=n; i++ ) for( int j=0; j<=n; j++ ) dp[i][j] = -INF;
		for( int i=1; i<=n; i++ ) dp[i][0] = 0;
		for( int i=1; i<=n-m; i++ ) M[i].clear(), W[i].clear();
		for( int i=1; i<=n-m; i++ ) {
			int k;
			scanf("%d", &k);
			for( int j=0; j<k; j++ ) {
				int v, w;
				scanf("%d%d", &v, &w);
				M[i].push_back(v);
				W[i].push_back(w);
			}
		}
		for( int i=n-m+1; i<=n; i++ ) scanf("%d", &in[i]);
		Init(1, 0);
		DFS(1, 0);
		int ans = 0;
		for( int i=m; i>=0; i-- ) if(dp[1][i] >= 0) { ans = i; break; }
		printf("%d\n", ans);
	}
	return 0;
}