点分治,一种适用于树上的优化过后的暴力算法。
渐进时间复杂度为 $\Theta(n\log _ 2n\cdot\alpha(n))$,其中 $\alpha(n)$ 为统计数据算法的渐进时间复杂度。
简介
点分治是一种经过优化的朴素暴力算法,俗称淀粉质。
这种算法通常用于树上统计问题。
算法原理
点分治,顾名思义,分而治之,进行点分治,首先要选择分治点。
经验,理论分析告诉我们,对于一个序列的分治,一般是采用选择中点($\frac{1}{2}$)为分治点(当然,也有一些奇怪的分治算法选择使用黄金分割比 $\phi-1\to 0.618$ 为分割),因为这样可以使得分治算法的渐进时间复杂度为 $\Theta(n\log _ 2n)$,那么我们把这个结论推广到树上,则分治点应当选择为树的重心。
树的重心
定义
树的重心也叫树的质心。找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后,生成的多棵树尽可能平衡。
以上文字来自百度百科——传送门,下面让我们用数学化语言描述一下树的重心。
设 $u$ 为树 $\text{T}$ 的重心,$\text{son} _ u$ 为 $u$ 的所有子树的根节点(此时把 $u$ 看作根节点),$\text{size} _ x$ 表示以 $x$ 为根的子树的大小,那么满足:
$$\forall x\in\text{T}, \max _ {v\in\text{son} _ x}{\text{size} _ v}\geq\max _ {a\in\text{son} _ u}{\text{size} _ a}$$
从上面的定义,我们不难看出,一颗树可能有两个重心,例如:

上图中的树有两个重心,分别是 $2$ 和 $3$。
性质
- 树中所有点到某个点的距离和中,到重心的距离和是最小的,如果有两个重心,他们的距离和一样。
- 把两棵树通过一条边相连,新的树的重心在原来两棵树重心的连线上。
- 一棵树添加或者删除一个节点,树的重心最多只移动一条边的位置。
- 一棵树最多有两个重心,且相邻。
应用
利用这些性质,我们可以看出,树的重心把树分割成 $\lfloor\frac{n}{2}\rfloor$ 颗小树(甚至更小),所以递归的层数不超过 $\lceil\log _ 2n\rceil$,所以点分治的渐进时间复杂度为 $\Theta(n\log _ 2n\cdot\alpha(n))$。
代码
int root,MaxPart,sum;
// root 为树的重心
// MaxPart 为当前找到最大部分的最小值
// sum 为当前树(子树)的大小
int size[MAXN];
// size[i] 记录以 i 为根节点的大小
bool del[MAXN];
// del[i] 表示 i 是否已经被删除
/**/
root=-1,MaxPart=INF;
/**/
inline void GetRoot(reg int ID,reg int father){
reg int MaxSon=0;
size[ID]=1;
for(reg int i=head[ID];i;i=Next[i])
if(to[i]!=father&&!del[to[i]]){
GetRoot(to[i],ID);
size[ID]+=size[to[i]];
MaxSon=max((int)MaxSon,size[to[i]]);
}
MaxSon=max((int)MaxSon,sum-size[ID]);
if(MaxSon<MaxPart)
root=ID,MaxPart=MaxSon;
return;
}
算法流程
- 找当前树(子树)的重心,渐进时间复杂度为 $\Omega(n) $;
- 处理信息,渐进时间复杂度为 $\Omega(n)$;
- 统计信息,渐进时间复杂度为 $\Omega(\alpha(n))$;
- 删除重心,递归(或结束),渐进时间复杂度为 $\Theta(1)$。
上述流程最多进行 $\lceil\log _ 2n\rceil$ 次,总的渐进时间复杂度为 $\Theta(n\log _ 2n\cdot\alpha(n))$。
简单例题 & 题解
- [x] 聪聪可可:Luogu P2634/BZOJ 2152
题解:传送门 - [ ] Luogu P2664 树上游戏
题解:传送门 - [ ] Luogu P3345 [ZJOI2015]幻想乡战略游戏
题解:传送门 - [ ] Luogu P3676 小清新数据结构题
题解:传送门 - [ ] Luogu P3714 [BJOI2017]树的难题
题解:传送门 - [ ] Luogu P3727 曼哈顿计划E
题解:传送门 - [x] Luogu P3806 「模板」点分治1
题解:传送门 - [ ] Luogu P3920 [WC2014]紫荆花之恋
题解:传送门 - [ ] Luogu P4075 [SDOI2016]模式字符串
题解:传送门 - [ ] Luogu P4115 Qtree4
题解:传送门 - [x] Race:IOI 2011 Day 1 T2/Luogu P4149/BZOJ 2599
题解:传送门 - [ ] Luogu P4178 Tree
题解:传送门 - [ ] Luogu P4183 [USACO18JAN]Cow at Large P
题解:传送门 - [ ] Luogu P4220 [WC2018]通道
题解:传送门 - [ ] Luogu P4292 [WC2010]重建计划
题解:传送门 - [ ] Luogu P4886 快递员
题解:传送门 - [ ] Luogu P5306 Transport
题解:传送门 - [ ] Luogu P5439 「XR-2」永恒
题解:传送门
近期评论