8738: BZOJ4738:汽水

Memory Limit:512 MB Time Limit:5 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

 牛牛来到了一个盛产汽水的国度旅行。这个国度的地图上有n个城市,这些城市之间用n?1条道路连接,任意两个城

市之间,都存在一条路径连接。这些城市生产的汽水有许多不同的风味,在经过道路 i 时,牛牛会喝掉wi的汽水 。牛牛非常喜欢喝汽水,但过量地饮用汽水是有害健康的,因此,他希望在他旅行的这段时间内,平均每天喝到的 汽水的量尽可能地接近给定的一个正整数k。同时,牛牛希望他的旅行计划尽可能地有趣,牛牛会先选择一个城市 作为起点,然后每天通过一条道路,前往一个没有去过的城市,最终选择在某一个城市结束旅行。牛牛还要忙着去 喝可乐,他希望你帮他设计出一个旅行计划,满足每天 |平均每天喝到的汽水-k| 的值尽量小(其中天数至少为1 ),请你告诉他这个最小值。


输入格式

第一行两个正整数n,k。 接下来n-1行,每行三个正整数ui,vi,wi,表示城市ui和城市vi之间有一条长度为wi的道路连接。 n≤5×10^4,0≤wi≤10^13,0≤k≤10^13。 同一行相邻的两个整数均用一个空格隔开。


输出格式

一行一个整数,表示 |平均每天喝到的汽水-k|的最小值的整数部分 即你只要将这个最小值向下取整然后输出即可。


样例输入

5 21
1 2 9
1 3 27
1 4 3
1 5 12

样例输出

1

提示

没有写明提示


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: