0x54 树形 dp/背包类树形 dp/选课 std.cpp 一处有误

[MicroMilo]

void dp(int x) {
	f[x][0] = 0;
	for (int i = 0; i < son[x].size(); i++) {
		int y = son[x][i];
		dp(y);
		for (int t = m; t >= 0; t--) 
			for (int j = 0; j <= t; j++)
                              f[x][t] = max(f[x][t], f[x][t-j] + f[y][j]);
			/* 或者
			for (int j = t; j >= 0; j--) // 经过实测，j 上界应为 m。树形结构的特殊性，y dp 过程已经结束，而 x 第二维度浅层次还未开始
				if (t + j <= m)
					f[x][t+j] = max(f[x][t+j], f[x][t] + f[y][j]);
                        */
	}
	if (x != 0)
		for(int t = m; t > 0; t--)
			f[x][t] = f[x][t-1] + s[x];
}

[lydrainbowcat]

书上的写法也没问题的呀，它在哪个数据上出错了吗？

从t推到t+j，和考虑t从t-j推过来，是dp的两种写法，没什么本质区别吧

[MicroMilo]

可能我没有表达清楚，在该仓库中的std.cpp注释下的一种写法中，如下所示，会 WA。书上的写法是没问题的

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
vector<int> son[310];
int f[310][310], s[310], n, m;

void dp(int x) {
	f[x][0] = 0;
	for (int i = 0; i < son[x].size(); i++) {
		int y = son[x][i];
		dp(y);
		for (int t = m; t >= 0; t--) 
			for (int j = t; j >= 0; j--) // 若将 j 的初值替换为 m，可以 AC
				if (t + j <= m)
					f[x][t+j] = max(f[x][t+j], f[x][t] + f[y][j]);
	}
	if (x != 0)
		for(int t = m; t > 0; t--)
			f[x][t] = f[x][t-1] + s[x];
}

int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i++)
	{
		int x;
		cin >> x >> s[i];
		son[x].push_back(i);
		
	}
	memset(f, 0xcf, sizeof(f)); // -INF
	dp(0);
	cout << f[0][m] << endl;
}

hack 数据为

10 5
0 4
0 6
1 2
0 1
2 8
4 9
3 7
5 1
8 2
2 4