Processing math: 100%

[BZOJ 3252]攻略

danihao123 posted @ 2017年11月27日 13:24 in 题解 with tags 贪心 bzoj 树链剖分 , 689 阅读
转载请注明出处:http://danihao123.is-programmer.com/

近期心情不顺,坑了一堆没写的题解……(嗯我反演等回来再填坑吧(逃

好了还是说说这题吧,私以为鄙人的做法还是蛮妙的:

定义d(x)表示x到根上所有点的权值和,dmax(x)x所在的子树中所有点的d(x)的最大值。对一个结点,他的所有儿子中dmax(x)最大的称为重儿子,其他作为轻儿子,然后做一遍树剖。然后将所有重链的权值和扔到一个数组里,降序排序,选前k大求和即可(不够的话全选)。

为什么?

显然,尽可能选叶子是划算的。然后,任意一条重链链顶的父亲所在的重链的权值和必定大于该重链,所以说不必担心某个重链选了而他的祖先却没有被记到答案里的情况。而若干这种重链的并,恰好对应了若干条到叶子路径的并。由于我们还是从大到小选的,所以答案是最优的。

代码:

Tripura Board Questi 说:
3 年前

Tripura Board Model Paper 2023 Class 4 Pdf Download with Answers for Bengali Medium, English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Questions to Term1 & Term2 Exams at official website. Tripura Board Question Paper Class 4 New Exam Scheme or Question Pattern for Sammittive Assignment Exams (SA1 & SA2): Very Long Answer (VLA), Long Answer (LA), Small Answer (SA), Very Small Answer (VSA), Single Answer, Multiple Choice and etc.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter