点分治入门

摘要

莫名其妙发现这几天遇到了很多点分治的题目,于是来系统整理一下点分治算法

点分治是一种树上分治算法。通常用于解决无根树上的统计问题。对于统计的问题,可以按照结点对其分类,分别统计后再组合成结果。而这类问题的求解复杂度往往和树的深度、大小有关,因此需要适当调整树的结构来使算法更加高效

例题引入

给定一棵有 n 个点的(边)加权无根树,m 次询问树上长度为 k 的简单路径是否存在.

.(来源:洛谷模板题)

朴素算法可以枚举端点然后计算长度,存到 bool 数组里,回答每个询问,复杂度 .

初步构思

如果我们把这棵树变成一颗有根树,那么不难发现路径可以分类。我们按照路径上深度最小的结点来分类,把路径归到结点分类中。对于根结点而言,和它有关的路径就是经过根结点的路径(包括端点的情况)。对于结点 而言,和它有关的就是它的子树内经过它的路径。可见这种分类的方法能够保证不重不漏.

利用这种分类,我们尝试统计路径的信息。我们选定一个根结点 ,然后统计和它有关的信息,统计完后,我们将它从树中删除,然后树就会变成若干个连通块(每个连通块是原树的子树)。我们可以对这些连通块递归进行相同的操作,统计对应的信息。

考虑这样的算法为什么是不重不漏的。对于一条路径,它要么经过根结点,要么就不经过根结点。如果经过根结点的话,我们就会在当前的递归状态下去统计;如果不经过根结点的话,就一定可以放在根结点的子树的连通块中处理。这就保证了不重不漏.

sample

复杂度调整

上文保证了算法的正确性,但是算法的效率如何?这取决于当前选择的根结点的位置以及统计一个结点的信息的复杂度. 我们会在每次选择当前子树的重心 作为根结点,因为重心可以使得删除后最大的连通块最小. 而统计一次信息的复杂度显然和当前子树的大小有关。稍后我们会简单证明,点分治的复杂度是 ,其中 是对整棵树的根结点统计一次信息的复杂度.

我们考虑如何统计经过当前根结点的路径的存在性。在遍历 的子结点 的时候,我们统计 子树下的点到 的距离并记录下来,放在 数组里。

同时我们维护 bool 数组 表示在 的子树下,长度为 的以 为端点的路径是否存在。然后我们双重循环遍历所有的 ,判断它们的差是否在 中存在,进而回答询问。然后把 中出现的长度标记到 中,然后清空 . 这样我们就完成了对当前根结点的信息统计。

复杂度 . 算上点分治的复杂度,总复杂度 .

算法框架

点分治算法的大致过程如下:

  1. 对于当前连通子树的根结点统计信息
  2. 把根结点从这棵树中删除,使得这个树分割为若干个连通子树
  3. 对于每一个连通子树,把它的重心作为它的根结点,重复上述过程

初始的时候,我们选择整棵树的重心作为根结点。

复杂度略证

由于每次都是找数的重心,所以处理完一个大小为 的树后,它的每个子树,大小都是最大为 ,所以最多分治 层,每层的问题空间都是 ,故时间复杂度为 .

下面给出一种代码实现.

重要变量声明 含义
vis[i] 表示结点 i 是否被删除了
sz[i] 当前状态下子树 i 的大小
mp[i] maxpart, 当前情况下 i 的子结点中 sz 的最大值(用来确定重心)
cur 当前子树大小
ctr 当前重心
#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,INF=0x3f3f3f3f,K=1e7+5;

struct qxx{int nex,t,v;};
qxx e[N*2];
int h[N],cnt;
void add_path(int f,int t,int v){e[++cnt]=(qxx){h[f],t,v},h[f]=cnt;}

int n,m;
int query[105];

bitset<N> vis;// 记录该点是否已删除
int sz[N],mp[N],cur,ctr;// 当前子树大小, 最大的连通块大小, 当前整个树的大小,当前重心
void getcenter(int u,int p){// 计算 sz
    sz[u]=1,mp[u]=0;
    for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t;
        if(v==p||vis[v])continue;
        getcenter(v,u),sz[u]+=sz[v];
        mp[u]=max(mp[u],sz[v]);
    }
    mp[u]=max(mp[u],cur-sz[u]);
    if(mp[u]<mp[ctr])ctr=u;    
}
bitset<K> curex;// 当前点分治下的路径存在性统计
int dis[N];
int expath[N],expcnt;
void getdis(int u,int p){expath[++expcnt]=dis[u];// 记录这次出现的路径
    for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t;
        if(v==p||vis[v])continue;
        dis[v]=dis[u]+e[i].v,getdis(v,u);
    }
}
void calc(int u){// 计算和 u 有关的问题 
    curex[0]=1;// 长度为 0 的路径
    for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t;
        if(vis[v])continue;
        expcnt=0,dis[v]=e[i].v,getdis(v,u);// 对子树 v 计算到 u 结点的距离
        for(int j=1;j<=expcnt;j++)for(int k=1;k<=m;k++)
            if(query[k]>=expath[j]&&curex[query[k]-expath[j]])query[k]=-1;// 达成询问
        for(int j=1;j<=expcnt;j++)curex[expath[j]]=1;// 标记出现的以 u 为端点的路径
    }
    curex.reset();}
void divid(int u){// 对 u 所在的连通块做点分治,u 不一定是根结点
    vis[u]=1;// 标记
    calc(u);// 计算和 u 有关的问题
    for(int i=h[u];i;i=e[i].nex){const int &v=e[i].t;
        if(vis[v])continue;// 已被点分
        cur=sz[v];// 这个 sz 是建立在上一次 u 的点分的基础上的
        mp[ctr=0]=INF;// 重心的 maxpart 初始化为无穷大
        getcenter(v,v),divid(ctr);// 对 v 所在的连通块做点分治
    }
}

int main(){scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++){int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add_path(a,b,c),add_path(b,a,c);
    }
    for(int i=1;i<=m;i++)scanf("%d",&query[i]);
    cur=n,mp[ctr=0]=INF,getcenter(1,1),divid(ctr);
    for(int i=1;i<=m;i++)puts(query[i]==-1?"AYE":"NAY");
    return 0;
}

  转载请注明: Sshwy's Blog 点分治入门

 上一篇
镇海省选集训 Day1 镇海省选集训 Day1
摘要 镇海中学的都是神仙吧 A.Line 平面上有 n 条两两不同的直线 ,现在给出一个左下角为 右上角为 的矩形,问有多少个直线对
2019.03.17
下一篇 
讲题 讲题
摘要 Day2T1 无向图对每种权值判断是否有边(没边就做完了),每次删边判连通 50 分直接计算,复杂度 . 从小到大枚举权值 动态图问题,要求支持加边,删边,问图是否连通 如果只有加边,可以用并查集判断是否连通 发现在
2019.03.07
  目录