点分治
点分治,顾名思义,是在树上进行分治算法。即递归在儿子上进行分治。但是这样的算法在随机数据下表现优秀,但一旦碰到单链或者多链的情况便难以处理,于是我们要引入一下概念。
概念
- 重心
树的重心:某一棵树的重心即以重心为根时,其最大子树大小最小。或者说,删除重心后,其子树形成的森林尽量均匀
知道重心有什么用呢,那么重心有一个重要性质
重心的子树大小小于$n/2$
这就很有用了,显然我们以重心为根进行操作,复杂度就降到了$O(nlogn)$
证明略。。。
作用
解决树上各种奇奇怪怪的边之间关系的问题
算法流程
算法流程大概如下(其中ans为最终结果)
|
|
代码大概如下:
|
|
例题
只做过最裸的,动态的未来更新吧(今天搞搞别的分治)
树上的点对
求树上两点间距离$dis(u,v)≤k$的对数
解法:
树分治,套用以上模板,计算的时候呢,计算出来所有的$depth$后,放入一个数组,进行排序,利用类似于迟取的思想快速计算出有几对即可。
code:
|
|
聪聪可可
求树上两点间路径权值和模$3$等于$0$的对数(无序)。
对于一个节点,等于$0$的有$x$对,等于$1$的有$y$对,等于$2$的有$z$对,那么一共满足的就有$x^2+2yz$对,然后还是套模板。。。。
code: