点分治学习笔记

· · 个人记录

大概是退役前学的最后一个算法了吧写个学习笔记纪念一下。

先来看这样一个问题。

例题 [洛谷P3806]【模板】点分治1

给定一棵有 N 个点的树，询问树上距离为 k 的点对是否存在。

假定该树的根节点为 root 。

那么树上的路径可以分为两类：

  1. 经过根节点 root。
  2. 包含于 root 的某一棵子树中（不经过根节点）。

第二类路径可以划分到 root 的子树中，因而可以考虑分治求解，将其作为子问题。

所以对于每个子问题只需考虑第一类路径，定义函数 calc(u) 表示处理以 u 为根的子树中第一类路径中是否有距离为 k 的点对。

对于一个第一类路径 x\to y ，可以将其分成 x\to root 与 root->y 两段。

令 d[x] 表示 x 到 root 的距离， b[x] 表示点 x 属于根节点的哪一棵子树。

那么对于一个询问 k ，就是判断是否有以下点对 (x,y) 存在：

令 a 数组表示在以 root 为根的子树中的点集，将其按照 d 的值排序，令其内的元素个数为 cnt 。

使用两个指针 l,r 分别从前后扫描 a 数组。其中 l 初值为 1，r 初值为 cnt 。

在指针 l 从左向右扫描的过程中，使得 d\big[a[l]\big]+d\big[a[r]\big]=k 的指针 r 的范围是单调递减的，因为已经将 a 数组排了序。

那么可以将询问离线，然后针对每个询问处理， 过程中不断移动指针，判断是否有满足上面条件的点对即可。

整个点分治算法过程如下：

  1. 任选一个根节点 root。
  2. 从 root 出发，预处理出 a,d,b 数组。
  3. 执行 calc(root)。
  4. 删除根节点 root，对 root 的每棵子树递归执行 1\sim 4 步。

假设递归的层数为 T 的话，那么整个算法时间复杂度为 O(TN\log N) 。

如果是链的话，那么时间复杂度将会退化到 O(N^2\log N) ，看上去是个很暴力的时间复杂度。

如何优化？这时候便要介绍树的重心的概念了。

树的重心

定义：对于一颗 n 个节点的无根树，找到一个点，使得把树变成以该点为根的有根树时，最大子树的节点数最小。换句话说，删除这个点后最大连通块（一定是树）的节点数最小。

——引自《算法竞赛入门经典》刘汝佳

树的重心的性质：

  1. 以这个点为根，那么所有的子树（不算整个树自身）的大小都不超过整个树的大小的一半。

  2. 树中所有点到某个点的距离和中，到重心的距离和是最小的；如果有两个重心，那么它们的距离和一样。

  3. 把两个树通过一条边相连得到一个新的树，那么新的树的重心在连接原来两个树的重心的路径上。

  4. 把一个树添加或删除一个叶子，那么它的重心最多只移动一条边的距离。

那么具体该如何求出树的重心呢？

可以根据上面树的重心的定义来求。

首先任选一点为根，把无根树化为有根树。

令 size[u] 表示以 u 为根的子树中的节点个数。

令 maxn[u] 表示删除节点 u 后最大连通块的节点数。

首先显然

size[u]=\sum_{v\in son_u}size[v]

删去节点 u 后，整个树分成若干个连通块，这些连通块分两类，一类是以节点 u 的子节点为根的子树，另一类是整个树去掉以 u 为根的子树的部分。

那么便可以推得

maxn[u]=\max\{size[v],n-size[u]\},v\in son_u

最终 maxn 值最小的节点就是树的重心。

核心函数：

int size[N],maxn[N],root;
void get_root(int u,int fa,int S) {
    size[u]=1,maxn[u]=0;
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].v;
        if(v==fa||vh[v]) continue;
        get_root(v,u,S);
        size[u]+=size[v];
        maxn[u]=max(maxn[u],size[v]);
    }
    maxn[u]=max(maxn[u],S-size[u]);
    if(!root||maxn[u]<maxn[root]) root=u;
}

函数中 S 表示整棵树的大小。

代码中 G 即为树的重心。

问题回到洛谷的这个模板题。

知道了树的重心有啥用？

以树的重心为根，那么其每个子树的大小都不会超过 \dfrac{N}{2} 。

那么在递归时，总层数为 O(\log N) ，那么这样的话总时间复杂度为 O(N\log^2N) 。其实是可以类比序列问题的分治的，相当于每次选择一个中间点，即相当于 T(N)=2T(N/2)+O(kN\log N) ，解是 T(N)=O(kN\log^2N) 。

如此，每个子问题都以当前子树的重心为根，即可 O(N\log^2 N) 求解。

代码

#include<bits/stdc++.h>
#define N 10010
#define DEBUG printf("vzyx and tqzer AK IOI!\n")

using namespace std;

inline int read() {
    int w=1,x=0;
    char ch=0;
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return w*x;
}

int head[N],tot=0;
struct graph{
    int v,w,next;
}edge[N<<1];
inline void add_edge(int u,int v,int w) {edge[++tot].v=v,edge[tot].w=w,edge[tot].next=head[u],head[u]=tot;}
inline void add(int u,int v,int w) {add_edge(u,v,w),add_edge(v,u,w);}

int n,m,k[N];
bool vh[N],flag[N];
int size[N],maxn[N],root=0,a[N],b[N],d[N],cnt;
bool cmp(int x,int y) {
    return d[x]<d[y];
}
void get_root(int u,int fa,int S) {
    size[u]=1,maxn[u]=0;
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].v;
        if(v==fa||vh[v]) continue;
        get_root(v,u,S);
        size[u]+=size[v];
        maxn[u]=max(maxn[u],size[v]);
    }
    maxn[u]=max(maxn[u],S-size[u]);
    if(!root||maxn[u]<maxn[root]) root=u;
}
void get_db(int u,int fa) {
    a[++cnt]=u;
    b[u]=b[fa];
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].v,w=edge[i].w;
        if(v==fa||vh[v]) continue;
        d[v]=d[u]+w;
        get_db(v,u);
    }
}
void calc(int u) {
    cnt=0;
    a[++cnt]=u;
    d[u]=0;
    b[u]=u;
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].v,w=edge[i].w;
        if(vh[v]) continue;
        b[v]=v,d[v]=w;
        get_db(v,v);
    }
    sort(a+1,a+cnt+1,cmp);
    for(int i=1;i<=m;i++) {
        if(flag[i]) continue;
        int l=1,r=cnt;
        while(l<r) {
            if(d[a[l]]+d[a[r]]>k[i]) r--;
            else if(d[a[l]]+d[a[r]]<k[i]) l++;
            else if(b[a[l]]==b[a[r]]) {
                if(d[a[r]]==d[a[r-1]]) r--;
                else l++;
            }
            else {
                flag[i]=true;
                break;
            }
        }
    }
}
void solve(int u) {
    vh[u]=true;
    calc(u);
    for(int i=head[u];i;i=edge[i].next) {
        int v=edge[i].v,w=edge[i].w;
        if(vh[v]) continue;
        root=0;
        get_root(v,v,size[v]);
        solve(root);
    }
}

int main() {
    n=read(),m=read();
    for(int i=1;i<n;i++) {
        int u,v,w;
        u=read(),v=read(),w=read();
        add(u,v,w);
    }
    for(int i=1;i<=m;i++) {
        k[i]=read();
        if(!k[i]) flag[i]=true;
    }

    get_root(1,1,n);
    solve(root);

    for(int i=1;i<=m;i++) {
        if(flag[i]) printf("AYE\n");
        else printf("NAY\n");
    }

    return 0;
}

总结

点分治可以用来解决树上路径信息问题，且较为高效。

参考资料

《算法竞赛入门经典》

《算法竞赛进阶指南》

Froggy dalao的题解