点分治，一种适用于树上的优化过后的暴力算法。
渐进时间复杂度为 $\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」永恒
题解：传送门
近期评论