题意
给出一棵树，每个节点有权值，问由 \(1\) ~ \(n\) 个节点组成的树块的权值和的最小值。
分析
首先发现 \(n\) 很小，那么我们可以开一个二维数组 \(dp[i][j]\) 表示以 \(i\) 节点为树块的根节点且树块中节点的数量为 \(j\) 时的最小值。
从 \(u\) 节点出发，先去遍历子树，再用子树的那个根节点 \(v\) 去更新 \(u\) 的值。code
#include#include #include #include using namespace std;typedef long long ll;const int MAXN = 2e3 + 10;const ll INF = 1e18;int n;int w[MAXN];vector G[MAXN];ll dp[MAXN][MAXN];int sons[MAXN];void dfs(int fa, int u) { dp[u][1] = w[u]; sons[u] = 1; for(int i = 0; i < (int)G[u].size(); i++) { int v = G[u][i]; if(v != fa) { dfs(u, v); sons[u] += sons[v]; for(int j = sons[u]; j >= 1; j--) { for(int k = 1; k <= sons[v]; k++) { if(j <= k) break; if(dp[v][k] == INF) break; dp[u][j] = min(dp[u][j], dp[u][j - k] + dp[v][k]); } } } }}int main() { scanf("%d", &n); for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { dp[i][j] = INF; } scanf("%d", &w[i]); } for(int i = 1; i < n; i++) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u); } dfs(-1, 1); for(int i = 1; i <= n; i++) { ll ans = INF; for(int j = 1; j <= n; j++) { ans = min(ans, dp[j][i]); } printf("%lld%c", ans, " \n"[i == n]); } return 0;}