专栏首页数据结构与算法洛谷P4383 [八省联考2018]林克卡特树lct(DP凸优化/wqs二分)

洛谷P4383 [八省联考2018]林克卡特树lct(DP凸优化/wqs二分)

题目描述

小L 最近沉迷于塞尔达传说:荒野之息(The Legend of Zelda: Breath of The Wild)无法自拔,他尤其喜欢游戏中的迷你挑战。

游戏中有一个叫做“LCT” 的挑战,它的规则是这样子的:现在有一个N 个点的 树(Tree),每条边有一个整数边权vi ,若vi >= 0,表示走这条边会获得vi 的收益;若vi < 0 ,则表示走这条边需要支付- vi 的过路费。小L 需要控制主角Link 切掉(Cut)树上的 恰好K 条边,然后再连接 K 条边权为 0 的边,得到一棵新的树。接着,他会选择树上的两个点p; q ,并沿着树上连接这两点的简单路径从p 走到q ,并为经过的每条边支付过路费/ 获取相应收益。

海拉鲁大陆之神TemporaryDO 想考验一下Link。他告诉Link,如果Link 能切掉 合适的边、选择合适的路径从而使 总收益 - 总过路费最大化的话,就把传说中的大师之剑送给他。

小 L 想得到大师之剑,于是他找到了你来帮忙,请你告诉他,Link 能得到的 总收益 - 总过路费最大是多少。

输入输出格式

输入格式:

从文件lct.in 中读入数据。

输入第一行包含两个正整数N; K,保证0 <= K < N <= 3* 10^5105 。

接下来N - 1 行,每行包含三个整数xi; yi; vi,表示第i 条边连接图中的xi; yi 两点, 它的边权为vi。

输出格式

输出到文件lct.out 中。

输出一行一个整数,表示答案。

输入输出样例

输入样例#1: 复制

5 1
1 2 3
2 3 5
2 4 -3
4 5 6

输出样例#1: 复制

14

说明

【样例1 解释】

一种可能的最优方案为:切掉(2; 4; ?3) 这条边,连接(3; 4; 0) 这条边,选择(p; q) = (1; 5)。

• 对于10% 的数据,k = 0 ;

• 对于另外10% 的数据,k = 1 ;

• 对于另外15% 的数据,k = 2 ;

• 对于另外25% 的数据,k <= 100 ;

• 对于其他数据,没有特殊约定。

对于全部的测试数据,保证有1 <= N <= 3 * 10^5105 ; 1 <= xi; yi <= N; |vi| <= 10^6106 。

【提示】

题目并不难。

当时在考场上,,只会$k=0$还挂了一个点。。

题目等价于:在树上选择$k+1$条不相交的链,使其权值和最大。

考虑树形DP(以下的$k$均为$k+1$)

一个很直观的想法是用$f[i][j]$表示第$i$个节点,子树中选了$j$条链的最大价值。

但这样是无法转移的,因此我们要考虑到根节点的情况,

令$f[0/1/2][i][j]$表示$i$号节点的子树中选了$j$条链,根节点不在任何一条链中/作为链的端点/作为两条链的端点的最大值。

更新的时候分三种情况讨论。

但是这样复杂度是$O(N*K)$的,考虑继续优化。

看到这种带$k$限制类的问题,我们尝试wqs二分

按照套路,我们观察$f$数组在不同的$k$下的最优解,不难发现函数是上凸的。严格证明不会,自己意会一下吧。。

按照套路,二分一个边权,加到每条边上,我们可以通过控制边权来控制$k$的大小。如果边权都很小,肯定是少选几条链比较优,如果边权比较大,肯定是多选几条优。

按照套路,如果我们二分到一个边权,在这里恰好选了$k$条链,那么这种选法就是最优的。

判断的时候不需要枚举$k$,因此DP一遍的复杂度为$O(N)$,总复杂度为$O(NlogV)$

还有就是这玩意儿二分的边界比较诡异。。。

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<vector>
#define Pair pair<int, int>
#define int long long 
const int MAXN = 3 * 1e5 + 1;
using namespace std;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    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;
}
struct Node {
    int x, y;//x :权值   y:数目 
    bool operator < (const Node &rhs) const {
        return this -> x == rhs.x ? this -> y > rhs.y : this -> x < rhs.x;//tag
    }
    Node operator + (const Node &rhs) const {
        return (Node) {x + rhs.x, y + rhs.y};
    }
    Node operator + (const int &rhs) const {
        return (Node) {x + rhs, y};
    }
}f[3][MAXN];
int N, K;
struct Edge {
    int u, v, w, nxt;
}E[MAXN << 1];
int head[MAXN], num = 0;
inline void AddEdge(int x, int y, int z) {
    E[num] = (Edge) {x, y, z, head[x]};
    head[x] = num++;
}
int mid;
Node Plus(Node a) {
    return (Node){a.x - mid, a.y + 1};
}
void dfs(int x, int fa) {
    f[2][x] = max(f[2][x], (Node) {-mid, 1});
    for(int i = head[x]; i != -1; i = E[i].nxt) {
        int v = E[i].v;
        if(v == fa) continue;
        dfs(v, x);
        f[2][x] = max(f[2][x] + f[0][v], Plus(f[1][x] + f[1][v] + E[i].w));//把根与子树连起来,会增加一条链 
        f[1][x] = max(f[1][x] + f[0][v], f[0][x] + f[1][v] + E[i].w);
        f[0][x] = f[0][x] + f[0][v];
        //printf("%d %d %d\n", f[2][x].x, f[1][x].x, f[0][x].x);
    }
    f[0][x] = max(f[0][x], max(Plus(f[1][x]), f[2][x]));
}
main() {
#ifdef WIN32
    freopen("a.in", "r", stdin);
#endif  
    memset(head, -1, sizeof(head));
    N = read(); K = read() + 1;
    int l = 0, r = 0;
    for(int i = 1; i < N; i++) {
        int x = read(), y = read(), z = read();
        AddEdge(x, y, z); AddEdge(y, x, z);
        r += abs(z);
    }
    l = -r;
    while(l <= r) {
        mid = (l + r) >> 1;
        memset(f, 0, sizeof(f));
        dfs(1, 0);
        if(f[0][1].y <= K) r = mid - 1;
        else l = mid + 1;
    }
    mid = l; memset(f, 0, sizeof(f));
    dfs(1, 0);
    printf("%lld", f[0][1].x + mid * K);
    return 0;
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU4609 3-idiots(生成函数)

    但是如果直接算合法的方案的话会出现一点问题。我们在算的时候维护了一个后缀和表示乘起来大于等于这个数的方案。我们要求的方案需要满足i < j < k,但是这样计算...

    attack
  • HDU5036 Explosion(期望 bitset)

    首先根据期望的线性性,可以转化为求每个点的期望打开次数,又因为每个点最多会被打开一次,只要算每个点被打开的概率就行了

    attack
  • 洛谷P2881 [USACO07MAR]排名的牛Ranking the Cows(bitset Floyd)

    显然如果题目什么都不说的话需要\(\frac{n * (n - 1)}{2}\)个相对关系

    attack
  • 南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 H. Holy Grail 多源最短路

    用户2965768
  • HDU4609 3-idiots(生成函数)

    但是如果直接算合法的方案的话会出现一点问题。我们在算的时候维护了一个后缀和表示乘起来大于等于这个数的方案。我们要求的方案需要满足i < j < k,但是这样计算...

    attack
  • CodeForces #549 Div.2 C Queen

    ShenduCC
  • View的工作原理

    View的绘制流程是从ViewRoot的PerformTraversals方法开始的。它经过measure,layout,draw三个过程将view绘制出来。m...

    提莫队长
  • LeetCode 593. 有效的正方形(数学)

    Michael阿明
  • 图论--LCA--树上倍增法(在线)

    风骨散人Chiam
  • Topcoder SRM 698 Div1 250 RepeatString(dp)

    attack

扫码关注云+社区

领取腾讯云代金券