网站首页
编程语言
数据库
系统相关
其他分享
编程问答
P10641
2024-06-21
题解:P10641 BZOJ3252 攻略
我让cz搬这道题,cz给搬了,于是来写个题解(考虑一个朴素的贪心:每次选择一个到根路径价值和最大的叶子,将价值和累加进答案,并把这条链价值清零。这个贪心的正确性显然(可以交换法证明),很容易用数据结构维护做到\(O(n\logn)\)。但是这样太不优美了,而且数据结构比较难写,于是考虑一个