挺有意思的树型 dp。
思路
发现直接求解很难对限制下手。
但我们可以注意到答案最多为 \(n\)。
考虑将答案记录 dp 状态。
我们可以记 \(dp_{i,j}\) 为子树 \(i\) 合法并且断了 \(j\) 条边的状态。
由于合法状态有两种,并且不好一起考虑,所以可以再在 dp 状态中加一维。
令 \(dp_{i,j,0/1}\) 为子树 \(i\) 内共断了 \(j\) 条边,不是/是全部都为正数的最小和。
转移是简单的,自行推导即可。
时间复杂度:\(O(n^2)\)。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int s[5010];
int a[5010];
int g[5010][5010][2];
int t[5010][2];
vector<int> to[5010];
inline void dfs(int x, int f) {
s[x] = 1;
if (a[x] < 0) g[x][0][0] = a[x];
if (a[x] > 0) g[x][0][1] = a[x];
for (auto i : to[x]) {
if (i == f) continue;
dfs(i, x);
memset(t, 0x3f, sizeof t);
for (int j = 0; j <= s[i]; j++)
for (int k = 0; k <= s[x]; k++) {
t[j + k][0] = min(t[j + k][0], g[i][j][0] + g[x][k][0]);
t[j + k][0] = min(t[j + k][0], g[i][j][1] + g[x][k][0]);
t[j + k][0] = min(t[j + k][0], g[i][j][0] + g[x][k][1]);
t[j + k][1] = min(t[j + k][1], g[i][j][1] + g[x][k][1]);
if (g[i][j][0] < 0 || g[i][j][1] < 1e17) t[j + k + 1][0] = min(t[j + k + 1][0], g[x][k][0]);
if (g[i][j][0] < 0 || g[i][j][1] < 1e17) t[j + k + 1][1] = min(t[j + k + 1][1], g[x][k][1]);
}
s[x] += s[i];
memcpy(g[x], t, sizeof t);
}
}
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 2; i <= n; i++) {
int u, v;
cin >> u >> v;
to[u].push_back(v);
to[v].push_back(u);
}
memset(g, 0x3f, sizeof g);
dfs(1, 0);
for (int i = 0; i <= n; i++) {
if (g[1][i][0] < 0 || g[1][i][1] < 1e17) {
cout << i << "\n";
return 0;
}
}
}
标签:5010,0x3f,int,题解,Tree,dfs,Attack,dp
From: https://www.cnblogs.com/JiaY19/p/18400233