点分治学习笔记

导言

淀粉质点分治是一种统计方法,具体来说,是对树上的点的一些值来进行统计,标准的点分治统计复杂度为 O(Nlog^2N) 是解决树上疑难杂症的不三之选(还有一个是树形dp)

算法思路&&具体问题

【洛谷P3806】点分治

给你一棵树,有m个询问,每个询问包含一个k,问树中是否存在距离为k的点对

这是一道很好的模板题,在这道题里面,我们具体关注点分治的想法与实现,其中有些地方复杂度会爆炸(还是能过),这里我们不做讨论

很容易得到一个 O(N^2) 的算法,我们首先选一个点,然后再枚举第二个点。

但是别忘了,这是一棵树。

随便一颗树

假设最上面的那个节点是根,那么所有经过它的所有路径有什么特点?

  1. 以它为端点。
  2. 经过它。

把这些路径统计起来后,对于每个子树也统计这样的路径(注意要把根删掉),不断进行这样的分治,路径就被不重不漏地统计出来了
基于分治的思想,我们需要用树的重心来作为根。

于是这一题就轻松地写出来啦

轻松的A了上面一题之后,突然觉得点分治很简单(然而这只是我的错觉),这是因为上面的点分治是“假的”,下面这一题可以说明问题出在哪

【P2634】聪聪可可

给你一棵树,问你有多少个点对之间的距离能被3整除

有了上一题的经验,于是套上了点分治的模板,然后就TLE了QAQ,60Pt

问题就出在我们统计路径的时候没有做到O(N),一般来说,题目中总会有些特殊的性质来帮助你在这一步可以做到O(N)

比如这一题,我们可以用以下策略来统计:

  1. 保存d数组时保存的是 mod 3 后的余数,并统计每种值的数量储存在yu数组里面
  2. 根节点的 yu[0]^2+2yu[1]yu[2] 加入答案(0+0的路径还是3的倍数,1+2的路径也是3的倍数,后面的*2是排列顺序不同,前面不*2是因为两个距离根为0的点已经被yu[0]统计了,它们都在里面)
  3. 上面一个肯定有重复(在同一子树内的点对也被统计到了),于是我们对于每一棵子树,再减去 yu[0]^2+2yu[1]yu[2] (这里不是分治)
  4. 再进行分治

P4149 [IOI2011]Race

给一棵树,每条边有权。求一条简单路径,权值和等于K,且边的数量最小。

这一题其实和一开始的模板题没两样,只不过数据范围很大,统计路径的时候不能再O(N^2)

用一棵平衡树来维护就行(set足够)

由于这是存在性问题,所以不用在意统计子树时的重复统计

发表评论

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