NOIP2015 运输计划

题意简述

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

解题思路

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


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


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


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


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

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

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


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


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

时间复杂度 \mathcal{O}((n + m) \log w)

代码实现

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

查看评论