#P4738. 汽水

    ID: 3858 传统题 2000ms 512MiB 尝试: 125 已通过: 57 难度: 9 上传者: 标签>难度分类提高+/省选-树算法点分治排序与序列处理二分答案构造与建模绝对值分段线性化同向双指针贪心保留最优候选CF2600

汽水

题目描述

牛牛来到一个盛产汽水的国度旅行。这个国度的 nn 个城市由 n−1n-1 条双向道路连接,任意两个城市之间都存在路径。经过第 ii 条道路时,牛牛会喝 wiw_i 单位的汽水。

牛牛可以选择任意城市作为起点,每天沿一条道路到达一个未去过的城市,至少走一天。他想使每天饮用的汽水量的平均值尽可能接近给定的 kk。若所选旅行经过 dd 条道路,总共喝了 ss 单位的汽水,求 ∣sd−k∣\left|\frac{s}{d}-k\right| 的最小值。

输入格式

第一行包含两个整数 n,kn,k。城市编号为 11 至 nn。

接下来 n−1n-1 行,每行包含三个整数 ui,vi,wiu_i,v_i,w_i,表示城市 ui,viu_i,v_i 之间有一条道路,经过时喝 wiw_i 单位的汽水。同一行相邻的整数用一个空格隔开。

输出格式

输出一个整数,表示 ∣sd−k∣\left|\frac{s}{d}-k\right| 的最小值向下取整后的结果。

样例 #1

样例输入 #1

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

样例输出 #1

1

数据范围

n≤5×104n\le5\times10^4,0≤wi,k≤10130\le w_i,k\le10^{13}。旅行至少经过一条道路。