f[u][j] 表示以 u 为根的子树如果删掉j条边且跟u断开连接的连通块 >= 0 的情况下，跟u相连的部分的最大值是多少。
然后做一个树上背包即可。树上背包时间复杂度O(n^2)
最大答案就是求一个最大的 ans, 满足 f[1][ans] >= 0
参考代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int inf = INT_MAX / 3;
const int N = 2000 + 10;
vector<int> g[N];
int n, m, sz[N], f[N][N * 2], fa, a[N], dp[N];
void dfs(int u) {
sz[u] = 1;
f[u][0] = a[u];
for (int v : g[u]) {
dfs(v);
for (int j = sz[u] + sz[v] - 1; j >= 0; --j) dp[j] = -inf;
for (int j = sz[u] - 1; j >= 0; --j)
if (f[u][j] != -inf)
for (int k = min(sz[u] + sz[v] - 1 - j, sz[v] - 1); k >= 0; --k)
if (f[v][k] != -inf) {
if (f[v][k] >= 0) {
dp[j + k + 1] = max(dp[j + k + 1], f[u][j]);
}
dp[j + k] = max(dp[j + k], f[u][j] + f[v][k]);
}
for (int j = sz[u] + sz[v] - 1; j >= 0; --j) f[u][j] = dp[j];
sz[u] += sz[v];
}
}
signed main() {
cin >> n;
for (int i = 0; i <= n; ++i)
for (int j = 0; j <= n; ++j) f[i][j] = -inf;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
for (int i = 2; i <= n; ++i) {
int fa;
cin >> fa;
g[fa].push_back(i);
}
dfs(1);
for (int i = n - 1; i >= 0; --i)
if (f[1][i] >= 0) {
cout << i << endl;
return 0;
}
cout << -1 << endl;
return 0;
}