c/c++开发分享洛谷P3177[HAOI2015]树上染色(树上背包)

题意

题目链接

sol

比较套路吧，设(f[i][j])表示以(i)为根的子树中选了(j)个黑点对答案的贡献

然后考虑每条边的贡献，边的两边的答案都是可以算出来的

转移的时候背包一下。

#include #define pair pair #define fi first #define se second #define mp(x, y) make_pair(x, y) #define ll long long  const int maxn = 2001, inf = 1e9 + 7; using namespace std; inline int read() {     int x = 0, f = 1; char c = getchar();     while (c <&＃39;0&＃39; || c > &＃39;9&＃39;) {if (c == &＃39;-&＃39;) f = -1; c = getchar();}     while (c >= &＃39;0&＃39; && c <= &＃39;9&＃39;) x = x * 10 + c - &＃39;0&＃39;, c = getchar();     return x * f; } int n, k, siz[maxn]; ll f[maxn][maxn]; vector v[maxn]; void dfs(int x, int fa) {     siz[x] = 1; f[x][1] = f[x][0] = 0;     for(int i = 0; i = 0; j--)              for(int k = 0; k <= min(siz[to], j); k++)                 if(f[x][j - k] >= 0)                 f[x][j] = max(f[x][j], f[x][j - k] + f[to][k] + 1ll * k * (k - k) * w + 1ll * (siz[to] - k) *  (n - (k - k) - siz[to]) * w);     } }  main() {     n = read(); k = read();     for(int i = 1; i <= n - 1; i++) {         int x = read(), y = read(), w = read();         v[x].push_back(mp(y, w));         v[y].push_back(mp(x, w));     }     memset(f, -0x7f, sizeof(f));     dfs(1, 0);     cout <