「OI」点分治

点分治,一种适用于树上的优化过后的暴力算法。

渐进时间复杂度为 $\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}$$

从上面的定义,我们不难看出,一颗树可能有两个重心,例如:

Tree-Point-Divide-Z1.webp

上图中的树有两个重心,分别是 $2$ 和 $3$。

性质

  1. 树中所有点到某个点的距离和中,到重心的距离和是最小的,如果有两个重心,他们的距离和一样。
  2. 把两棵树通过一条边相连,新的树的重心在原来两棵树重心的连线上。
  3. 一棵树添加或者删除一个节点,树的重心最多只移动一条边的位置。
  4. 一棵树最多有两个重心,且相邻。

应用

利用这些性质,我们可以看出,树的重心把树分割成 $\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;
}

算法流程

  1. 找当前树(子树)的重心,渐进时间复杂度为 $\Omega(n) $;
  2. 处理信息,渐进时间复杂度为 $\Omega(n)$;
  3. 统计信息,渐进时间复杂度为 $\Omega(\alpha(n))$;
  4. 删除重心,递归(或结束),渐进时间复杂度为 $\Theta(1)$。

上述流程最多进行 $\lceil\log _ 2n\rceil$ 次,总的渐进时间复杂度为 $\Theta(n\log _ 2n\cdot\alpha(n))$。

简单例题 & 题解