题意简述

给定一棵带权树，再给出几条路径，可以把一条边边权修改成零，问你这些路径长度中最大值最小是多少

解题思路

看到最大值最小很自然联想到二分答案
二分什么？

考虑二分一个 表示当前路径长度最大不能超过 。那么对于那些长度超过 的路径，我们就需要修改。这里假设有 条吧。
路上那么多边，改哪一个？或者，哪一些？

一个很自然的想法是修改边权最大值。但很不凑巧，如果仅仅有一条路径经过了这条边，那么修改这条边仅仅会对一条路径产生影响，其他的路径长照旧大于 。
怎么办？

接着往下想，发现对所有路径产生影响的边是这些路径的公共边。所以现在的问题转化成了：找出几条路径的公共边中权值的最大的边。

这玩意的充分条件也不大好想。考虑一下必要条件：

一条边为 条路径的公共边的必要条件是它被所有路径经过 次。

很容易发现，这其实是个充要条件。
所以问题转化成了：找出被 条路径覆盖 次的所有边。

路径覆盖一次，也就是遍历的时候在所有边上记一笔，也就是树上的区间加；最终查询的时候遍历所有边，挨个查询有没有记够 笔，也就是单点查询。
差分立解。

令差分数组 diff[u] 表示 u 连到它父亲那条边的覆盖次数（的差分值）。
修改的时候直接 ++diff[u], ++diff[v], diff[LCA] -= 2。
查询的时候从子树往上合并，每次 diff[u] += diff[v]。
如果往下合并的话，因为一个点往往有多条边，可能导致不知道该合并到哪个子树里去。算是一个常用套路。
最后 遍历一遍所有的边，查一下哪些边 diff = t，取个最大值。
如果 最大的路径长 减掉 这个边权最大值 仍然大于 就 return false，否则 return true

时间复杂度 。

代码实现

代码就不放了。一直卡 65 分，至今没调完。调完再放。