给定一棵树以及树上的 mmm 条通路，我们可以在树上选取一条边，将其权重置为 000，目标是                                                  min                    max通路权重将某条边的权重重置0\ \ \ \ \ \ \ \ \ \ \\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ min\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ max通路权重\\将某条边的权重重置0                                                  min                    max通路权重将某条边的权重重置0 20PTS(M=1) 当 m=1m=1m=1 时，我们只需要求出树上的一条链上的权重和与权重最大值即可。 50PTS 考虑一种暴力的算法，枚举将哪一条边权重置 000，然后重新在树上求解 mmm 条通路的权重。这个过程可以用 LCA 优化。任选一个结点为根，预处理出每一条通路的两个端点的 LCA，则路径长度可以通过树上差分快速计算。时间复杂度为 O(n(n+m))O(n(n+m))O(n(n+m))。 80PTS(树退化为链) 当树退化为链时，这就是一个纯粹的数据结构问题。这类最小化最大值的问题可以考虑二分答案，将其转化为判定问题。给定一个权重上界 w ww 后，我们可以 O ( m ) O(m)O(m) 算出哪些通路的权重是超过这个上界的，而这些通路全部位于一条链上，因此我们可以 O ( m ) O(m)O(m) 求出它们的交集。然后在交集中找到权重最大的一条边，如果将这条边的权重置 000 后，所有通路的权重均不超过 www，那么 www 就是一个可行的上界。 100PTS 上面的二分答案方法给了我们初步的思路。现在只需考虑树上给定权重上界后如何判定：首先任取一个结点作为根结点，并将边权下推为点权。使用差分维护数组 f[v]f[v]f[v] 表示从 vvv 的父结点到 vvv 的这条边被经过了多少次。假设有 cntcntcnt 个权重超过上届的通路，那么我们只要考虑被经过 cntcntcnt 次的边即可。 AC代码