0 碎碎念

实数二分，永远的调不出来(｡◕∀◕｡)

但是这算法还挺有意思的，故写到博客

1 题目大意

给定一棵树，每个结点两个权值 a,b 。

令一个合法的方案为一个点 u 和一个点集 v，满足以下要求

• $\forall x \in v$ ，满足 x 是 u 子树中的结点（包括 u 本身）
• $\sum b_{v_i} \leq m$

令一个方案的贡献为 $a_u \cdot |b|$

求最大贡献

-1 申请

在今年五月的时候突然发现 PKU 和 THU 要举办夏令营的消息先后到来

THU 的报名不需要学生做什么，我就没有在意。 PKU 的报名需要填写不少资料还需要去打印并盖章申请书。人不在鸟市，就让教练帮忙了。

随后前往镇海中学参加训练。

天天都有的考试一直持续到 10 号，虽然 THU 方面似乎抛弃了新疆一直没有给我们教练回话，但是 PKU 还是通过了我的申请。

0 Day 0

5.13 镇海中学 -> 宁波火车站 -> 余姚北站 -> 余姚中学

在上午考试的时候向镇海教练询问，发现他们将会于明天早上出发。考虑到由镇海到余姚由 1h + 的车程，但我并没有教练或者家长随行，故选择在 13 日自行前往余姚。

0 说在之前

正常来说，一个正常的 Oier 是不会碰这种东西

但是我们综合实践小组的组长不知道为啥对这东西出奇的感兴趣， 我就试着理解一下

因为也仅仅是试着理解，如有理论错误还往各位在评论区斧正

本文的代码实现可以在 https://gitee.com/yingziyu/task 看到

1 树上启发式合并

1.1 启发式算法

我并没有找到比较正式的定义，在这里引用 OI Wiki 里的

启发式算法是基于人类的经验和直观感觉，对一些算法的优化。

例子：并查集的按秩合并

1.2 树上启发式合并

基于「减少节点多的子树的处理次数」的思想为主的算法

1.3 实现

我们希望节点多的子树处理次数尽可能少，也就是我们希望重儿子的处理次数尽可能少

注意到许多树上问题的处理过程是可延续的，即当前子树的处理完后可以直接将数据移交到父亲节点继续处理

基于这点，我们可以优先处理重儿子，然后直接继承到父亲节点。这样对于一个节点来说，其重儿子只需要处理一次，其轻儿子需要处理两次。

因为从树上任意一条路径上，关键点（即轻儿子）在 $O(\log(n))$ 范围内，所以这东西的复杂度是 $O(n\log(n))$ 的。