QTREE4[三种做法]

凑!树链剖分重写n遍……编译的勇气都没有……

显然是我树链剖分的姿势不对……导致一些奇怪的问题……【我才不会告诉你我不会从斜堆里删一个元素呢……】

主席教了我点分治怎么做……现在我总共知道有三种做法了


回顾题面:

一棵边带权树:初始全部都是白点,支持两种操作

1.修改一个点的颜色——黑变白,白变黑

2.查询全局最远两个白点的距离

与zjoi某题的最大区别就是这题边是有负权的

SOL

树链剖分

先转有根树……

考虑把树树链剖分,对于每个点,维护以它为两个白点LCA时的最长距离……询问时取全局最大,修改时想办法修改 ——基本想法

实现方法:

轻重链剖分后,每个点有一个重子节点以及若干个轻子节点,我们维护从这个点向下能到的最远的白色节点的距离的最大值与次大值(注意这两条向下的路径不能有边重叠,如果不存在这么多白节点就记作-INF)……

怎么求这个最大值和次大值呢?

我们把考虑的这个节点的所有轻子节点的向下的最大值用一个堆维护,然后询问这个节点重子节点的最大值,这样就能快速得到最大值和次大值了……

对于一个重链……我们得到了每个节点沿非重子节点向下的最大距离和次大距离之后

可以用线段树维护(类似连续子段和)……来得到沿重链的最大距离balabala……

就这样了……如果没有看懂请去看 漆子超论文……

T_T 然后我们发现要维护线段树,就要维护堆,要维护堆,还要指望维护下一级线段树……这种嵌套关系非常复杂……再加上树链剖分固有的代码长度……代码难度非常大

边分治

考虑边分治,我们每次选一个边,维护这个边左端点连下去的子树的最大距离,右端点下去的最大距离,然后左端点连下去的距离同样用堆维护,右端点也用堆维护,这样就能快速合并两个子树的答案了……

因为是边分治……所以要对树做等价处理防止因为树的形态而产生时间复杂度的退化

同样如果没有看懂请去看 漆子超论文或者搜索……

以上两种办法都是主流做法……

点分治

主席教我开大招!

传送门

hza说点分治常数大?主席点分治过了打脸23333

请戳这里看14L的发言

一下是主席介绍的方法

选重心,类似的,和边分治一样做下去……来看怎么合并答案,将重心所有延伸下去的子树到白节点的最长距离用堆 维护……这样就好了……

每次修改往上搞,最多修改O(log n)个堆……所以每次修改是O(log^2 n)的

优势就是这样子就不用担心被菊花形的数据卡了……而且非常暴力非常好想……

堆可以用zkw线段树实现,也可以用stl的优先队列(主席用stl的过了)

主席的点分治代码


感觉自己说得还是太含糊 …… 点分治还是说详细一点好了……

点分治的优点在于好想以及相对好写……

首先点分治后……树被分成了若干层,每一层有若干个重心……我们用一个堆维护跨越所有这些重心的白路径的最大值,不妨称它为全局堆——Globe Heap

我们要取答案时只需要得到Globe的最大值就好了……

考虑如何维护Globe

一个重心有若干个子树,我们用一个堆来维护一个重心的所有子树的向下延伸到一个白节点的最大距离,这样就可以快速维护一个重心的答案了……不妨称一个重心的子树堆为Root Heap……
这样我们就会有很多Root Heap……

由Root Heap得到跨越这个重心的最长白路径只需要取出最大值和次大值加到一起就可以了……

更新时用Root Heap维护Globe就好了……

但是如何维护Root Heap呢……

我们继续增加heap……弄出一个front heap[][]数组……

表示第i层,第j个节点(这个节点在这一层的父亲即第i层的一个重心)向下到一个白节点的最大值……这样就可以快速维护Root了……front heap可以直接快速维护……

就解决了

我的点分治代码就不贴了……和主席基本上差不多……

Comments

comments powered by Disqus