Description

小L最近沉迷于塞尔达传说:荒野之息(The Legend of Zelda: Breath of The Wild)无法自拔
他尤其喜欢游戏中的迷你挑战。
游戏中有一个叫做“LCT”的挑战,它的规则是这样子的:现在有一个N个点的树(Tree),每条边有一个整数边权
vi,若vi>=0,表示走这条边会获得vi的收益;若vi<0,则表示走这条边需要支付-vi的过路费。小L需要控制主角L
ink切掉(Cut)树上的恰好K条边,然后再连接K条边权为0的边,得到一棵新的树。接着,他会选择树上的两个点p
;q,并沿着树上连接这两点的简单路径从p走到q,并为经过的每条边支付过路费/获取相应收益。海拉鲁大陆之神T
emporaryDO想考验一下Link。他告诉Link,如果Link能切掉合适的边、选择合适的路径从而使总收益-总过路费最
大化的话,就把传说中的大师之剑送给他。小L想得到大师之剑,于是他找到了你来帮忙,请你告诉他,Link能得
到的总收益-总过路费最大是多少。

Input

输入第一行包含两个正整数N;K,保证0<=K<N<=3*10^5
接下来N-1行,每行包含三个整数xi;yi;vi,表示第i条边连接图中的xi;yi两点,它的边权为vi。
1 <= N <= 3 * 10^5
1 <= xi; yi <= N; |vi| <= 10^6

Output

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

Sample Input

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

Sample Output

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

HINT

请不要提交!数据如下:https://begin.lydsy.com/JudgeOnline/upload/lct.rar
原题面:www.lydsy.com/JudgeOnline/upload/201804/day2(3).pdf

Source

n*k^2 的做法

考虑原题转化为选取k+1条不想交的链使得权值最大

设dp[0/1/2][x][k]表示当前在x节点 x相连的边的度数为0,1,2 的最优答案

注意理解方程的定义即可 这个度数是是否与选中的链的度数 如1则代表我当前这条链从子树上来目前还没有到头

2表示我子树的链上来和我之前的链接上了 我夹在中间的时候度数是2 那么度数是0的时候同样适用于我这条度数为1的链上来被我封顶了 或者度数为2的链被我就此封顶了 均可在我的父节点中充当0度数的角色

 

满分做法

考虑将答案数组与k的函数图像画出来发现是上凸函数  那么这个是一个可以用wqs二分

考虑每次二分出的正比例函数用原函数减去现在的这个正比例函数

会发现,新图像将会在这个斜率对应点的位置最高,同时也是一个斜率递减函数

那么可以知道我斜率越大最高点也单调 个人感觉斜率大 可选的范围在变小 最高点可以考虑dp来求 最后我们求出的k比二分的斜率小的时候就需要减小斜率了

 


elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论