BZOJ 3252 攻略


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

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


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

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

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

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

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 3252 攻略


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , ,