#P18221. Enchanted Lawns Quest

Enchanted Lawns Quest

Enchanted Lawns Quest

Shrek 和 Donkey 来到一片魔法森林。森林中的 nn 块草坪由 n−1n-1 条双向小路连接,每两块草坪之间恰有一条简单路径,因此这些小路构成一棵树。每条小路有一个阻力值。

树的直径定义为:任意两块草坪之间的简单路径上,小路阻力之和的最大值。

他们一共有恰好 ww 单位魔法,可以给小路增加阻力。设第 ii 条小路原来的阻力为 aia_i,调整后的阻力为 bib_i,需要满足:

  • 对每条小路,bi≥aib_i\ge a_i;
  • 所有 bib_i 都是整数;
  • ∑i=1n−1bi=∑i=1n−1ai+w\sum_{i=1}^{n-1}b_i=\sum_{i=1}^{n-1}a_i+w,即必须用完全部 ww 单位魔法。

请最小化调整后树的直径,并输出这个最小值。

输入格式

第一行包含两个整数 n,wn,w。

接下来 n−1n-1 行,每行包含三个整数 vi,ui,aiv_i,u_i,a_i,表示草坪 vi,uiv_i,u_i 之间有一条初始阻力为 aia_i 的小路。

输出格式

输出一个整数,表示用完恰好 ww 单位魔法后,树的直径能够达到的最小值。无需输出具体分配方案。

数据范围

  • 2≤n≤2⋅1052\le n\le2\cdot10^5;
  • 1≤w≤10121\le w\le10^{12};
  • 1≤ui,vi≤n1\le u_i,v_i\le n;
  • 1≤ai≤1071\le a_i\le10^7;
  • 保证所有小路构成一棵树。

本题只有一组数据。

样例 1

5 7
1 2 2
1 3 4
1 4 5
3 5 2
14

样例 2

2 7
1 2 4
11

样例说明

样例 1 可以按原题下图分配魔法:将边 (1,2)(1,2) 的阻力从 22 增加到 77,边 (1,4)(1,4) 从 55 增加到 66,边 (3,5)(3,5) 从 22 增加到 33,其余边不变。共增加 5+1+1=75+1+1=7,调整后的直径为 1414。

原题样例1的一种魔法分配方式

样例 2 只有一条边,必须把全部 77 加到这条边上,直径成为 4+7=114+7=11。