BZOJ 3252 攻略


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

题意:选择 k 条从根到叶子的路径,拿走点权,点权只能拿一次,求最大和。


显然可以暴力链剖,是\(O(log_n^2)\) 的,很不优雅。

好像做法很多,我写了个长链剖分,链长即到链顶的权值和。维护一个堆,每次取叶子节点更新这个堆。

由于链不相交,所以不会重复计算点权,就可以了。

复杂度是\(O(nlog_{叶子个数})\) 的,跑的飞快。

 


一个蒟蒻oier的博客 |稍有常识的人都能看出,公告里已经说啦注册功能尚未恢复,不要再试啦~想要账号可以在任意一篇文章下评论留下联系方式或者私聊博主qq获取!~|目前存在某些题解latex数学格式丢失的问题,若遇到可以在该题解下回复,博主看到会修改!谢谢!