luogu#P4383. [八省联考 2018] 林克卡特树

    ID: 8410 远端评测题 10000ms 1000MiB 尝试: 4 已通过: 2 难度: 7 上传者: 标签>动态规划dp差分枚举暴力树的直径各省省选2018

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

题目描述

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

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

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

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

输入格式

输入第一行包含两个正整数 N,KN,K

接下来 N1N - 1 行,每行包含三个整数 xi,yi,vix_i,y_i,v_i,表示第 ii 条边连接图中的 xi,yix_i, y_i 两点,它的边权为 viv_i

输出格式

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

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

提示

样例解释

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

数据范围

  • 对于 10%10\% 的数据,k=0k = 0
  • 对于另外 10%10\% 的数据,k=1k = 1
  • 对于另外 15%15\% 的数据,k=2k = 2
  • 对于另外 25%25\% 的数据,k100k \leq 100
  • 对于其他数据,没有特殊约定。

对于全部的测试数据,保证 1N3×1051 \leq N \leq 3 \times 10^50K3×1050 \leq K \leq 3 \times 10^5K<NK \lt N1xi,yiN1 \leq x_i,y_i \leq Nvi106|v_i| \leq 10^6

提示

题目并不难。