忧心猫咪

文章
4
资源
0
加入时间
2年10月21天

洛谷 P2680 运输计划 树链剖分+LCA+树上差分+二分

洛谷 P2680 运输计划题意给你一个 nnn 个点的树,对于 n−1n-1n−1 条边各有边权,给出一些点对 (x,y)(x,y)(x,y) ,同时定义 dis(x,y)dis(x,y)dis(x,y) 表示 x,yx,yx,y 两点间的树上距离,现允许你将一条边的权值变为 000 ,请你最小化最大的 dis(x,y)dis(x,y)dis(x,y) 的值。解法为了使最长路径最短,考虑二分答案。那么如何判断 midmidmid 值是否可行呢。我们可以求出每一条路径的距离,如果这个距离大于