#2083. 汽水
汽水
汽水
题目描述
标题: 汽水 - Problem - QOJ.ac
The problem was used in the following contests:
牛牛来到了一个盛产汽水的国度旅行。
这个国度的地图上有 n 个城市,这些城市之间用 n−1 条道路连接,任意两个城市之间,都存在一条路径连接。这些城市生产的汽水有许多不同的风味,在经过道路 i 时,牛牛会喝掉 wi 的汽水。牛牛非常喜欢喝汽水,但过量地饮用汽水是有害健康的,因此,他希望在他旅行的这段时间内,平均每天喝到的汽水的量尽可能地接近给定的一个正整数 k 。
同时,牛牛希望他的旅行计划尽可能地有趣,牛牛会先选择一个城市作为起点,然后每天通过一条道路,前往一个没有去过的城市,最终选择在某一个城市结束旅行。
牛牛还要忙着去喝可乐,他希望你帮他设计出一个旅行计划,满足每天|平均每天喝到的汽水−k|的值尽量小,请你告诉他这个最小值。
输入格式
第一行两个正整数 n,k 。
接下来 n−1 行,每行三个正整数 ui,vi,wi,表示城市 ui 和城市 vi 之间有一条长度为 wi 的道路连接。
同一行相邻的两个整数均用一个空格隔开。
输出格式
一行一个整数,表示 |平均每天喝到的汽水−k| 的最小值的整数部分,即你只要将这个最小值向下取整然后输出即可。
样例一
input
5 21
1 2 9
1 3 27
1 4 3
1 5 12
output
1
explanation
在图中,路径5->1->3是一条最合适的路线,总计喝到的汽水的量是 27+12=39, 平均每天喝到的汽水量是 39÷2=19.5, |19.5−21|=1.5,向下取整后得到 1,因此答案是 1。
样例二
见下发文件。
限制与约定
对于 20% 的数据,n≤1000。
对于另外 20% 的数据,保证编号为 i(1≤i≤n−1) 的节点和编号为 i+1 的节点之间连接了一条边。
对于另外 20% 的数据,保证数据是以1为根的完全二叉树(在完全二叉树中,节点 i(2≤i≤n) 和节点 ⌊i÷2⌋ 之间有一条道路)。
对于另外 20% 的数据,保证除节点 1 以外,其他节点和节点 1 之间都有一条道路。
对于 100% 的数据,2≤n≤5×104,0≤wi≤1013,0≤k≤1013。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
5 21
1 2 9
1 3 27
1 4 3
1 5 12
1
样例 2
100 8851772802675
2 1 7846878805057
3 1 1091300025565
4 1 4413185271937
5 1 1402847866621
6 1 7272683446983
7 1 5713708188403
8 1 5015615909929
9 1 984580540903
10 1 1194018214609
11 1 445949127601
12 1 1797688349151
13 1 1919330142926
14 1 124541192601
15 1 1376770423627
16 1 6055779684481
17 1 1470345442651
18 1 3640583661001
19 1 2554532307251
20 1 6380983262717
21 1 74703012781
22 1 1815494300401
23 1 408962735875
24 1 7978533874837
25 1 1308360888171
26 1 893556635401
27 1 2133622689256
28 1 3014623205017
29 1 595751602201
30 1 605686132546
31 1 4578707074600
32 1 2376654263569
33 1 589194404785
34 1 334525199471
35 1 209140936291
36 1 858594740473
37 1 2510240430361
38 1 7972521690531
39 1 4908728886216
40 1 5667522894721
41 1 402715286921
42 1 874555458921
43 1 2766666315601
44 1 497243629081
45 1 332428745601
46 1 4697161237405
47 1 1613428680901
48 1 486145570813
49 1 2909247093217
50 1 274170021841
51 1 229280966881
52 1 1637487101251
53 1 2284865637913
54 1 6141570036289
55 1 869058787360
56 1 564379601221
57 1 4871849487199
58 1 9276160738627
59 1 2782070855841
60 1 285958850326
61 1 1883401578313
62 1 2211464891539
63 1 1964478562801
64 1 4607752633345
65 1 3507949567591
66 1 1255136702851
67 1 3696818730101
68 1 8748725577103
69 1 4100683342369
70 1 7910371721441
71 1 10649851627
72 1 495879726057
73 1 1096959424001
74 1 4740464847055
75 1 8490641425501
76 1 985961832153
77 1 2992308699401
78 1 6290954104621
79 1 583392803329
80 1 1275905666371
81 1 8090711293393
82 1 4992187502017
83 1 1255725421693
84 1 1128370070001
85 1 5909716121
86 1 61137687601
87 1 1425592828705
88 1 4802578454941
89 1 789164640181
90 1 6302884360321
91 1 375994234225
92 1 9369856680466
93 1 5209927163911
94 1 563896560301
95 1 5503596624481
96 1 604689881086
97 1 159531606092
98 1 843460695681
99 1 6111876493801
100 1 123451362441
31628279389