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

题意

题目链接

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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏写代码的海盗

乐呵乐呵得了 golang入坑系列

开场就有料,今天返回去看了看以前的文章,轻松指数有点下降趋势。一琢磨,这不是我的风格呀。一反思,合着是这段时间,脑子里杂七杂八的杂事有点多,事情一多,就忘了快乐...

3465
来自专栏追不上乌龟的兔子

[奇怪但有用的数据结构]并查集Union Find

严格来讲并查集并不是一个数据结构,而是一个算法,毕竟其英文名直译是联合查找,但作为一个系列,还是当做数据结构讲了。

6847
来自专栏数据结构与算法

POJ3622 Gourmet Grazers(FHQ Treap)

Description Like so many others, the cows have developed very haughty tastes an...

3245
来自专栏数据结构与算法

BZOJ1061: [Noi2008]志愿者招募(线性规划)

  申奥成功后,布布经过不懈努力,终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难

1294
来自专栏数据结构与算法

洛谷P4014 分配问题(费用流)

题目描述 有 nn 件工作要分配给 nn 个人做。第 ii 个人做第 jj 件工作产生的效益为 c_{ij}cij​ 。试设计一个将 nn 件工作分配给 nn ...

3657
来自专栏码农阿宇

NopCommerce开源项目中很基础但是很实用的C# Helper方法

刚过了个五一,在杭州到处看房子,不知道杭州最近怎么了,杭州买房的人这么多,房价涨得太厉害,这几年翻倍翻倍地涨,刚过G20,又要亚运会,让我这样的刚需用户买不起,...

42011
来自专栏行者悟空

利用Hadoop Mapreduce实现pv统计分析

2463
来自专栏lonelydawn的前端猿区

Node.js力破江苏网警刑侦科推理试题

月前,江苏网警 在微博发布了一套《2018年刑侦科目推理试题》,可谓难倒了诸多英雄好汉,评论区内更是一片皮皮之音。 @二向箔icon: 高考前班主任教过我们,...

3087
来自专栏tkokof 的技术,小趣及杂念

侃侃哈希表

说到哈希表,相信初通数据结构的人士应该耳熟能详,其相关的结构细节虽然并不繁复,但就快速查找数据而言,该结构优异的性能表现绝对可算一枝独秀,平均情况下O(1)的时...

721
来自专栏aCloudDeveloper

string 之 strlen函数

Author: bakari  Date: 2012/8/9 近两年好多的IT公司喜欢拿一些库函数来考,string函数库当然是首选,除此之外,像qsort,S...

1917

扫码关注云+社区