【NOIP2015】运输计划

CJOJ P2430 - 【NOIP2015】运输计划

题意

  有一颗n个节点的树，第 i 条边连接ui和 vi ，边权为 wi 。有m个任务，每个任务要从 si 前往 ti ，花费的时间是路径上的边权之和。

  现在可以选择一条边，让这条边的边权变为0,。请你求出如果选择边可以使得最大的花费时间最小化

解法

树链剖分+树上查分+线段树+二分：

  首先，在树上求大量的点对之间的距离就是用树链剖分，这里不多说过程

  其次就是最小化最大花费，采用二分的做法：

  二分答案 mid ，对于所有的 dis＞mid 的任务，我们将其路径标记出来。假设有 k 个任务超出限制，那我们需要将这k个任务 dis 全部减到 mid 之下，所以我们可以找到所有路径的公共边中的最长边 x ，判断dis max −wx 是否 ≤mid 即可

  现在的关键就在于如何找到这 k 条路径的公共边，如果使用线段树区间加法肯定会超时，所以使用树上差分。

  对于每一次从s前往 t ，将s, t 的权+1;将LCA(s,t)和 father[LCA(s,t)] 的权-1，一个点最终被覆盖的次数就是这个点所在子树的权和（因为边已经下放到了点上面，所以把覆盖次数记在点上借口）

  

复杂度

O（ nlogn+mlogm ）