HeinzHuang

Eudaimonia

0%

点分治

Posted on Edited on In

树上的分治分两种：点分治和边分治，点分治由于其比较稳定的复杂度，是两者中更为常用的一种。

点分治

顾名思义，就是将树用重心分割为几块，然后在每棵树中进行类似“暴力”的操作，已达到复杂度优化的作用 重心,即一棵树上的一个点，以其作为根，其最大子树大小最小的点

复杂度

考虑最坏情况，一个重心只有两个子树，那么当你如此分割时，两颗子树的大小都大概是原树大小的一半左右，若在每棵树中的操作都是O(n)的话，最后复杂度便为O(nlogn)，然而这是最坏情况，若平均起来，会比它还小一些，可见它是十分有效的。

模板

首先是找到树的重心，比较简单，一个深搜便能解决

伪代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
get_center(int x,int fa){
    siz[x]=1
    mx[x]=0
    for edge in x
        v=edge.to
        if v!=fa and vis[v]==0
            get_center(v,x)
            siz[x]+=siz[v]
            if mx[x]>siz[v] 
                mx[x]=siz[v]
    if t_sz-siz[x]>mx[x]
        mx[x]=t_sz-siz[x]
   if center==0 or mx[center]>mx[x]
       center=x     
}

这里应该都能看出，\(center\)就是重心，\(t_{sz}\)是整棵树的大小，其实就是递归求出所有子树的大小，再取最大值，同时不要忘了以父亲为根的子树 再然后就是\(vis\)，\(vis\)数组就相当于上面提到的分割点，也就是这个点已经被当做重心计算过了，不能递归走回去，所以也要判掉

接下来就是dfs了

伪代码：
1
2
3
4
5
6
7
8
9
10
11
12
dfs(int x){//x便是重心
    vis[x]=1
    work(x)
    for edge in x
        v=edge.to
        work(v)
        if v!=fa and vis[v]==0
            center=0
            t_sz=siz[v]
           get_center(v,x)
           dfs(center) 
}

这里就比较直观了，每次递归到一个重心后，将其用\(vis\)标记掉，这样接下来的\(work\)就是一道点分治题的精髓了，它代表你在当前的树中进行的操作或计算，在不同的题目中它的内容都不同。有时只work子树，有时根和子树都work，十分多变。

接下就是求出每个子树的\(center\)， 在递归下去继续计算即可！