欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

洛谷P3177 [HAOI2015]树上染色(树上背包)

程序员文章站 2022-04-30 09:46:46
题意 "题目链接" Sol 比较套路吧,设$f[i][j]$表示以$i$为根的子树中选了$j$个黑点对答案的贡献 然后考虑每条边的贡献,边的两边的答案都是可以算出来的 转移的时候背包一下。 cpp include define Pair pair define fi first define se ......

题意

题目链接

sol

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

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

转移的时候背包一下。

#include<bits/stdc++.h>
#define pair pair<int, int>
#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<pair> 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;
}