#P18221. Enchanted Lawns Quest
Enchanted Lawns Quest
Enchanted Lawns Quest
Shrek 和 Donkey 来到一片魔法森林。森林中的 块草坪由 条双向小路连接,每两块草坪之间恰有一条简单路径,因此这些小路构成一棵树。每条小路有一个阻力值。
树的直径定义为:任意两块草坪之间的简单路径上,小路阻力之和的最大值。
他们一共有恰好 单位魔法,可以给小路增加阻力。设第 条小路原来的阻力为 ,调整后的阻力为 ,需要满足:
- 对每条小路,;
- 所有 都是整数;
- ,即必须用完全部 单位魔法。
请最小化调整后树的直径,并输出这个最小值。
输入格式
第一行包含两个整数 。
接下来 行,每行包含三个整数 ,表示草坪 之间有一条初始阻力为 的小路。
输出格式
输出一个整数,表示用完恰好 单位魔法后,树的直径能够达到的最小值。无需输出具体分配方案。
数据范围
- ;
- ;
- ;
- ;
- 保证所有小路构成一棵树。
本题只有一组数据。
样例 1
5 7
1 2 2
1 3 4
1 4 5
3 5 2
14
样例 2
2 7
1 2 4
11
样例说明
样例 1 可以按原题下图分配魔法:将边 的阻力从 增加到 ,边 从 增加到 ,边 从 增加到 ,其余边不变。共增加 ,调整后的直径为 。

样例 2 只有一条边,必须把全部 加到这条边上,直径成为 。