我在学习点分治时,一直卡在这道题,今天我一鼓作气想尽办法终于把她 AC 了。

将要讲述的方法是动态点分治,有另一种链分治的方法个人感觉较为麻烦且不自然就不在此赘述。

首先静态点分治一遍建立点分树,并算出初始答案,存储每个节点作为重心时到上一个节点的边。当动态修改时从底层向上逐层修改直到抵达根节点。

对于每个节点,我们存储每个子树中距离最远的点(用 son 维护)和距离当前节点距离最远的点(用 hep 维护),最后再维护一个答案堆 ans 供查询。这个堆要资瓷添加和删除操作,可以用经典的建两个堆的方法,一个插入,一个删除即可。

其他当前子树中没有白色时应该返回 $-inf$ ,否则与当前子树的根节点是白色节点时等价的 qwq。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×