BZOJ4033 [HAOI2015] T1 【树形dp】
【题解】
看了zzq的博客过来也顺便填填坑。
介绍一种树上背包合并的方法:如本题
$f_{i, j}$表示以$i$为根的子树选$j$个,$i$为根的子树内的贡献加上$(i, fa_i)$的贡献的最大值。
转移就很好办啦!
# include <stdio.h> # include <algorithm> using namespace std; typedef long long ll; int n, k; ll f[2010][2010], g[20010]; int tot=0, head[200010], next[200010], to[200010], sz[200010], w[200010]; inline void add(int u, int v, int tw) { ++tot; next[tot] = head[u]; head[u] = tot; to[tot] = v; w[tot] = tw; } inline void dfs(int x, int fa, int v) { int siz = 1; for (int I=head[x]; I; I=next[I]) { if(to[I] == fa) continue; dfs(to[I], x, w[I]); int newsz = siz + sz[to[I]]; for (int i=0; i<=newsz && i<=k; ++i) g[i] = 0; for (int i=0; i<=siz && i<=k; ++i) { for (int j=0; j<=sz[to[I]] && j<=k; ++j) { if(i+j>k) continue; g[i+j] = max(g[i+j], f[x][i] + f[to[I]][j]); } } for (int i=0; i<=newsz && i<=k; ++i) f[x][i] = g[i]; siz = newsz; } sz[x] = siz; for (int i=0; i<=siz && i<=k; ++i) { if(siz + (k-i) > n) { f[x][i] = -666666666; continue; } f[x][i] += (ll)i*(k-i)*v; f[x][i] += (ll)(siz-i)*(n-siz-k+i)*v; } } int main() { scanf("%d%d", &n, &k); for (int i=1, u, v, tw; i<n; ++i) { scanf("%d%d%d", &u, &v, &tw); add(u, v, tw); add(v, u, tw); } dfs(1, 0, 0); printf("%lld\n", f[1][k]); return 0; }