P4383 [八省联考2018]林克卡特树lct

    • 473通过
    • 1.7K提交
  • 题目提供者 chen_zhe Aya
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 差分 枚举,暴力 树的直径 各省省选 2018 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 10000ms / 1024MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    警告:滥用本题评测将封号

    题目描述

    小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^5$。

    接下来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^5$; 1 <= xi; yi <= N; |vi| <= $10^6$ 。

    【提示】

    题目并不难。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。