点分治小结

何为点分治

在解决一些关于树上路径问题时我们常使用点分治。众所周知,一棵 n 个节点的树路径数是n^2的,点分治能将复杂度降为O(nlog^kn)k一般是1或2),尽管它也考虑了所有路径。

我们对树上的点分治,一般将路径分为到达这个点和从这个点出发的两条子路径。有时统计这些路径只能暴力解决(即将他们都走一遍),但是我们仍然可以使用一种节点的选择方法使得复杂度降低,就是选择子树的重心。然后我们继续对它的子树处理,因为我们已经考虑过经过这个点的路径了,所以我们便可以以它为中心将树劈开,分而治之。

定义

点分树,是在点分治时把各分治中心连在一起得到的一棵树。

练习

Luogu P3806【模板】点分治1

给定一棵有n个点的树,询问树上距离为k的点对是否存在。

分析

对于当前分治中心u,我们将经过u的路径分为两条。然后统计长度,计算数量。注意这时候会出现计算重复,即来自同一个子树的两个点的路径,我们再对每个子树额外计算一次并减去它即可。

当然这题比较实际上很鬼畜,每次都询问是会超时的,只能用一种复杂度不对的分治预处理好。

POJ 1741 Tree

给定一棵有n个点的树,询问树上距离小于等于k的点对数量。

分析

类似与上面的模板题,我们只需要暴力扫过子树后 two-pointer 搞一下就可以了。

BZOJ 2152 聪聪可可

求树上距离是3的倍数的点对数(有序点对)。

分析

还是一样的套路,路径对3取模后统计即可。

SCOI2016 幸运数字

有多组关于树上路径的询问。每次询问路径上点权集合子集的最大的异或和。

分析

对于求一个数集最大异或和,我们可以用线性基解决。但是线性基并不支持可持久化。考虑用暴力的点分治解决,对于每个分治中心,我们计算出它到分治子树中的每一个节点路径上的线性基,回答经过这个点的询问的时候,直接暴力合并两个线性基即可。时间复杂度O(n\log^2n).

Luogu P2664 树上游戏

在 Luogu 上切的第一道黑题,其实也没什么,就是代码写起来非常烦。

树上的每个点有一个颜色,定义s(u,v)uv路径上的颜色种数。设sum_u=\sum\limits_{v\in T}s(u,v),求所有点的sum.

分析

对于“种数”,直接计算会很慢。因此我们分开计算每种颜色的贡献即可。我们可以将问题转化为“枚举每种颜色,求从当前点出发,到树上所有点的路径中包含这种颜色的路径数量,并求和”。

然后我们可以分治统计贡献。对于当前分治中心uu的贡献来自两个地方:

  1. u出发到当前子树内点的路径
  2. u出发到 solved 的分治中心的点的路径

第一个贡献比较容易计算,对于第二个,我们可以计算对于其他点经过当前分治中心的贡献。因此这时候我们保证第二个贡献已经计算好了。至于如何计算经过当前点的贡献,无非也就两种情况(注意我们仍然需要暴力地遍历子树里的所有点给他累加,设当前子树内的点为v),我们还是按颜色考虑:

  1. 对于在vu的链上出现过的颜色,那么从v到当前子树外的点的路径都会产生贡献,即u的子树中除了v所在的子树其他子树大小之和。(注意这种贡献在同一条链上是要下传的)
  2. 对于没有在链上出现过的颜色,贡献是从u出发到其他其他子树中的路径产生的,我们可以计算出来。

至此,问题就解决了。不过这题实现仍有一些细节之处值得发掘,非常考验码力。

ZJOI2007 Hide 捉迷藏

这个应该算动态点分治入门题吧…

对下面一题有点启发,不过我是先做了下面一题再看到这题的。

给你一棵树,一开始所有点都是黑色,有一些操作会把一个点颜色反过来,询问树上最远两个黑点间距离。

分析

我们先建出点分树,然后每个点维护两个集合:

  1. 以该点为根的所有点分子树中的点到该点在点分树上的父亲的距离组成的集合;
  2. 以该点为根的所有点分子树中的儿子集合1中最大元素的集合.

实际实现可以用两个堆维护,其中一个用于打删除标记。并且我们还要维护一个答案集合。更新时在点分树上从下往上更新即可,注意细节和空间。

ZJOI2015 幻想乡战略游戏

dark幻想乡,dark题目…

树上每个点有一个权值d_u,开始都为0. 然后每次会对一个点的点权进行修改,增量可正可负,但保证点权一直非负。修改完后,询问对于树上固定的一点u\sum\limits_{v\in T}dist(u,v) * d_v的最小值。

分析

我们先来考虑在不带修的情况下如何求解。

首先对于相邻的两点uv,且uv的父亲,如果选vu优,那么考虑两者费用的差值。设c=cost(u,v),这时强制转u为根,sumd_u为所有点的d之和,sumd_vv的子树内的d之和。我们转移后的差值就是:

c(sumd_u-sumd_v-sumd_v)

如果v更优,那么应该有2sumd_v>sumd_u. 显然满足条件的v只有一个。

当然这里的重点在于证明了转移的唯一性,因此我们从任意一点出发,按照这个贪心策略转移,总是能找到最优点。当然,我们并不直接走到更优的相邻点(考虑一下树是链的情况,做点分的题目不能忘记这一点),因此,为了降低复杂度,我们选择都到相邻点子树的重心。

实际上,我们对于有修改时,直接去计算sumd是非常耗时的。不过我们可以选择直接计算出整个费用然后比较。注意到我们转移时选择的是树的重心,所以不妨先建出点分重构树,方便询问时直接在树上跑(注意重构时要记下从上一级分治中心到这个块的直接邻点)。接下来考虑如何直接在这个重构树上计算出总费用,并且要方便更新。我们在重构树上维护三个值:

  • sumd_u,以u为根节点的重构子树中d之和
  • ds1_u(我习惯称它为“屌丝1”),记录当前以u为根节点的重构子树中所有点到udist*d之和
  • ds2_u,记录当前以u为根节点的重构子树中所有点到u重构树上父亲dist*d之和

只需要这三个值,我们就可以每次O(logn)查询和修改了。

问题到这里就解决了。可以看出整个问题还是非常复杂的,特别是转移唯一性和最后维护的三个值比较难想到。

另外说一下关于点分重构树的问题,这道题是头一回遇到,其实它近似是一个立体结构,形状比较鬼畜的,这里有一张图,甚是形象。

点分重构树

About The Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注