题目链接

题解

令P为 各个路径上所有边权和 path, 所有的n-1条边记作: e1, e2, e3, ..., 比如:
P1 = e1 + e3 + e4 + ...
P2 = e2 + e3 + e5 + ...
P3 = e1 + e2 + e5 + ...

将一个ei (某一条边), 置为0后, 新的 各个路径PP1, PP2, PP3, ..
求: max( PP1, PP2, PP3, ...)的最小值.

---

看到 最少, 自然想到 二分.
令Check( mid)为: 将 某一条边权 置为0后, max( 所有的 路径和) 是否是 <= mid的. (如果是, 则r = mid)
这个定义自然是正确的.

---

错误思路

• 遍历所有的 路径, 如果PPi > mid (MAi为PPi路径上的 最大边权),
  如果所有的MAi <= (PPi - mid), 则说明 有解.

很容易这样想…
… 但是, 所有路径的MAi, 并不是同一条边呀…

---

正确思路
依旧是二分, Check的定义也依旧不变.
但一定要考虑一个核心问题: 我们只能选择同一条边, 将其置0,

令MA_PP = max( PPi) (即所有路径的最大值)
对于mid, 假设要置0的边为: E_choose
… 结论1: 则一定有: E_choose >= (MA_PP - mid), 这点非常关键!

我们只需考虑所有PPi > mid的路径, 假设这些路径是: PP1, PP2, ..., PPk
这些路径都是非法的, E_choose必须 同时在这些路径里!
因此
… 1, 建立树上对(边)的差分Diff (初始均为0)
… 2, 将PP1, ..., PPk这些路径上的 所有边, 都执行+= 1操作.
… 3, 将Diff恢复为Diff_sum
则, 同时出现在PP1, ... ,PPk这些路径上的边, 一定被 += 1 了 k次.
因此: 遍历所有的边 (其实遍历点就行, 因为差分的边权是在点上)
如果该边Diff_sum == k 且 该边的Wth边权 >= (MA_PP - mid), 两个条件, 则该边就是E_choose

---

思路就是这样的, 不算太复杂.

但操作比较多.
得到PPi需要用: 对(边权)的 树上前缀和.
将路径上所有边执行+= 1, 需要进行 对(边)的 树上差分, 然后再恢复
而且, 还需要通过点 获取边权值;

---

优化点

• 如果超时, 将 (二分区间) 缩小; MA_PP - max_edge, r = MA_PP (max_edge为 所有边的最大边)

---