洛谷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 < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}    while (c >= '0' && c <= '9') x = x * 10 + c - '0', 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 < v[x].size(); i++) {        int to = v[x][i].fi, w = v[x][i].se;        if(to == fa) continue;        dfs(to, x);        siz[x] += siz[to];    }    for(int i = 0; i < v[x].size(); i++) {        int to = v[x][i].fi, w = v[x][i].se;        if(to == fa) continue;        for(int j = min(siz[x], K); j >= 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 << f[1][K];    return 0;}