BZOJ 3252 攻略

发布于 2017-10-12  183 次阅读


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

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


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

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

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

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

 


一个非常弱的准退役OIER