题目描述

L 国有 n 个星球,还有 n-1 条双向航道,每条航道建立在两个星球之间,这 n-1 条航道连通了 L 国的所有星球。
小 P 掌管一家物流公司,该公司有很多个运输计划,每个运输计划形如:有一艘物流飞船需要从 ui 号星球沿最快的宇航路径飞行到 vi 号星球去。显然,飞船驶过一条航道 是需要时间的,对于航道 j,任意飞船驶过它所花费的时间为 tj,并且任意两艘飞船之 间不会产生任何干扰。
为了鼓励科技创新,L 国国王同意小 P 的物流公司参与 L 国的航道建设,即允许小 P 把某一条航道改造成虫洞,飞船驶过虫洞不消耗时间。
在虫洞的建设完成前小 P 的物流公司就预接了 m 个运输计划。在虫洞建设完成后, 这 m 个运输计划会同时开始,所有飞船一起出发。当这 m 个运输计划都完成时,小 P 的 物流公司的阶段性工作就完成了。
如果小 P 可以自由选择将哪一条航道改造成虫洞,试求出小 P 的物流公司完成阶段 性工作所需要的最短时间是多少?

题目分析

首先我们可以求出每一条路径长度,这个倍增求个lca,每个点到根节点距离dfs预处理即可。
接下来就不知道如何下手了对不对?

在不知道下一步该怎么办的情况下可以考虑二分答案。 ——沃·兹基朔德

好吧,那就二分答案吧。我们可以找出k条路径长度大于当前二分出的答案,所以要变成虫洞的那一条边一定会是这若干路径的交边。
于是我们使用树上差分和将每条边的影响落到终点的思想,即在路径两个端点处+1,在lca处-2。然后处理这个值。
这么处理:

获得的js值就是这条边在这若干个路径里经过的次数。然后选择边权最大的交边,看我们二分出来的答案是否可行即可。

代码