#PQJ394x2993. QOJ 394_2993

    ID: 2944 传统题 12000ms 1024MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:八省联合省选2018线段树

QOJ 394_2993

CCF NOI 2018 省队选拔赛 第二试林克卡特树(lct) 林克卡特树(lct) 【题目描述】 小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 × 105。 接下来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 第7 页 共10 页

CCF NOI 2018 省队选拔赛 第二试林克卡特树(lct) 【样例1 输出】 14 【样例1 解释】 一种可能的最优方案为:切掉(2, 4, −3) 这条边,连接(3, 4, 0) 这条边,选择 (p, q) = (1, 5)。 【样例2】 见选手目录下的lct/lct2.in 与lct/lct2.ans。 【子任务】 • 对于10% 的数据,k = 0 ; • 对于另外10% 的数据,k = 1 ; • 对于另外15% 的数据,k = 2 ; • 对于另外25% 的数据,k ≤100 ; • 对于其他数据,没有特殊约定。 对于全部的测试数据,保证有1 ≤N ≤3 × 105, 1 ≤xi, yi ≤N, |vi| ≤106 。 【提示】 题目并不难。 第8 页 共10 页