BZOJ 4326 NOIP2015 运输计划

发布于 2017-09-01  124 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4326

题意:带权无根树,给 m 组路径,每组路径的耗时为路径上边权和,有一次机会可以把一个边权变为 0,总费用记为每组路径耗时的最大值,求最小总费用。


被这狗题坑了半个下午...

还是很水的,最大值最小一眼二分答案。

怎么判定是否合法呢?看看是否存在一条边合法且是 m 条路径的交即可。

这个过程相当于树上路径+1,求是否存在一个权为 m,上链剖就太傻了。

差分统计,每次+1 相当于 lca-2,两个端点+1,然后一个点的点权就是子树和,从一个 usaco 题学来的技巧...

然后就可以了。但是直接上会在 UOJ 里 T 一个点... 优化一下常数,求子树和不递归了,维护 dfs 序扫一遍,然后就过了...

懒得继续卡常了 T.T

 

说一下自己被坑的经历吧 T.T

首先以为总费用是每组路径的耗时和,那就非常水了... 结果发现题解全写的啥玩意二分... 然后好久才反应过来题意看错了...

然后就是在 UOJ 里狂 T 不止... 代码有点丑... 将就看吧

 


一个非常弱的准退役OIER