柒葉灬 的博客

柒葉灬 的博客

点分治总结(个人笔记)

posted on 2018-12-19 14:54:46 | under 专题总结 |

点分治。


基础

首先得知道什么是点分治,点分治就是利用每次用 $O(n\times K)$ 计算一个块内的贡献,每一次将块至少缩小一半(树上重心,链上中点)来达到递归次数不超过 $logn$ 次,从而达到总复杂度不超过 $O(nlogn\times K)$ 的算法。

用一个实际栗子(模板题目)说明一下。

题目大意:给定一棵 $n$ 节点的树,问长度不超过 $K$ 的路径的个数。

如果我们假设每条路径必须穿过根

那么用 $O(nlogn)$ 的时间内就能算出来了,

把每个点到根的路径长度算出来,排序之后就可以查找了。

还剩下不经过根的点,把每个儿子所在的子树全部都这样算一遍,

这样的算法只能过完全二叉树的情况。

剩下来要做的就是把树变成完全二叉树,

具体做法是:每次找当前子树的重心

保证递归次数不超过 $logn$ 次。

知道这样子的话就可以差不多A掉这道题目了。

(需要注意的是:要把来自同一个子树的路径给删掉(容斥))

模板代码:

#include<bits/stdc++.h>
using namespace std;
template<class T>inline void tomax(T &a,T b){if(a<b)a=b;}
const int maxn=3e4+5;
int n,K,x,y,z,ans;
int tot,head[maxn],to[maxn*2],nxt[maxn*2],w[maxn*2];
void add_edge(int u,int v,int c){
    to[++tot]=v;
    nxt[tot]=head[u];
    w[tot]=c;
    head[u]=tot;
}
int Siz,rt,sz[maxn],mx[maxn];
int id,res[maxn];
bool vis[maxn];//已经处理过了 
void clear(){
    tot=0;
    memset(head,0,sizeof(head));
    memset(vis,0,sizeof(vis));
    ans=0;
}
void dfs_root(int f,int x){
    mx[x]=0;
    sz[x]=1;
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(y==f||vis[y])continue;
        dfs_root(x,y);
        tomax(mx[x],sz[y]);
        sz[x]+=sz[y];
    }
    tomax(mx[x],Siz-sz[x]);
    if(mx[x]<mx[rt]||rt==0)rt=x;
}
void dfs_dis(int f,int x,int Dis){
    res[++id]=Dis;
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(y==f||vis[y])continue;
        dfs_dis(x,y,Dis+w[i]);
    }
}
int solve_ans(int x,int D){
    id=0;
    dfs_dis(0,x,D);
    sort(res+1,res+1+id);
    int l=1,r=id,ans=0;
    while(l<r){
        while(l<r && res[l]+res[r]>K)r--;
        ans+=r-l;
        l++;
    }
    return ans;
}
void dfs(int x){
    vis[x]=1;
    ans+=solve_ans(x,0);
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(vis[y])continue;
        ans-=solve_ans(y,w[i]);
        rt=0;
        Siz=sz[y];
        dfs_root(x,y);
        dfs(rt);
    }
}
int main(){
    while(~scanf("%d%d",&n,&K),n!=0&&K!=0){
        clear();
        for(int i=1;i<n;i++){
            scanf("%d%d%d",&x,&y,&z);
            add_edge(x,y,z);
            add_edge(y,x,z);
        }
        Siz=n;rt=0;
        dfs_root(0,1);
        dfs(rt);
        printf("%d\n",ans);
    }
    return 0;
}

然而,有些题目不适合容斥写,

比如说不问你方案个数了,是最值问题,那么就不能这么写了。

其实点分治的板子还有另一种,逐个Query后再Update。

具体代码就像下面这样:

void add(int x){
    /*
    这里写修改的信息,
    一般如果是数组不清空的话,需要多传入top
    防止2条路径来自不同的块
    */
}
void calc(int x){
    /*
    这里写计算贡献
    同样记得如果数组不清空,多传入top
    */
}
void dfs_update(int f,int x){
    add(x);
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(y==f||vis[y])continue;
        dfs_update(x,y);
    }
}
void dfs_query(int f,int x){
    calc(x);
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(y==f||vis[y])continue;
        dfs_query(x,y);
    }
}
void solve_ans(int x){
    add(x);
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(vis[y])continue;
        dfs_query(x,y);
        dfs_update(x,y);
    }
}

进阶

动态点分治

动态点分治只要在上面的dfs函数里面多加一点东西就可以了。

void dfs(int f,int x){
    vis[x]=1;
    fa[x]=f;
    ans+=solve_ans(x,0);
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(vis[y])continue;
        ans-=solve_ans(y,w[i]);
        rt=0;
        Siz=sz[y];
        dfs_root(x,y);
        dfs(rt);
    }
}

不同的地方:

    fa[x]=f;

还是用例题来说

HDU4918 Query On the subtree

需要维护每个点到重心的贡献(动态开线段树),

而我们之前已经通过找重心的方法来使新树不超过 $logn$ 层了,

所以修改和查询的时候不会访问超过 $logn$ 个重心

注意修改的时候贡献来自同一个子树的情况,容斥掉,

多开 $n$ 棵线段树,维护到父亲重心的信息,

每次查询减掉就可以了,复杂度 $O(nlog^2n)$ 。

栗子题目的代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define debug(x) cerr<<"\t DEBUG: "<<#x<<" = "<<(x)<<endl
using namespace std;
const int maxn=1e5+5,maxm=2e7+5;
int n,q,x,y,A[maxn];
char c;
int id,head[maxn],to[maxn*2],nxt[maxn*2];
void add_edge(int u,int v){
    to[++id]=v;
    nxt[id]=head[u];
    head[u]=id;
}
int Fa[maxn],dep[maxn],top[maxn],son[maxn],Sz[maxn];
void dfs1(int f,int x){
    Fa[x]=f;
    dep[x]=dep[f]+1;
    Sz[x]=1;
    son[x]=0;
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(y==f)continue;
        dfs1(x,y);
        Sz[x]+=Sz[y];
        if(Sz[son[x]]<Sz[y])son[x]=y;
    }
}
void dfs2(int Top,int f,int x){
    top[x]=Top;
    if(son[x])dfs2(Top,x,son[x]);
    for(int i=head[x];i;i=nxt[i])
        if(to[i]!=f&&to[i]!=son[x])
            dfs2(to[i],x,to[i]);
}
int LCA(int a,int b){
    while(top[a]!=top[b]){
        if(dep[top[a]]>dep[top[b]])a=Fa[top[a]];
        else b=Fa[top[b]];
    }
    return dep[a]<dep[b]?a:b;
}
int Dis(int a,int b){
    return dep[a]+dep[b]-dep[LCA(a,b)]*2;
}
int tot,rt[maxn*2],lson[maxm],rson[maxm],sum[maxm];
void update(int &rt,int l,int r,int x,int num){
    if(!rt)rt=++tot;
    sum[rt]+=num;
    if(l==r)return;
    int mid=(l+r)>>1;
    if(x<=mid)update(lson[rt],l,mid,x,num);
    else update(rson[rt],mid+1,r,x,num);
}
int Query(int rt,int l,int r,int x){
    if(!rt||x==r)return sum[rt];
    int mid=(l+r)>>1;
    if(x<=mid)return Query(lson[rt],l,mid,x);
    else return sum[lson[rt]]+Query(rson[rt],mid+1,r,x);
}

int root,Siz,fa[maxn],sz[maxn],mx[maxn];
bool vis[maxn];
void dfs_root(int f,int x){
    sz[x]=1;mx[x]=0;
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(y==f||vis[y])continue;
        dfs_root(x,y);
        mx[x]=max(mx[x],sz[y]);
        sz[x]+=sz[y];
    }
    mx[x]=max(mx[x],Siz-sz[x]);
    if(mx[x]<mx[root]||root==0)root=x;
}
void dfs(int f,int x){
    fa[x]=f;
    vis[x]=1;
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(vis[y])continue;
        Siz=sz[y];
        root=0;
        dfs_root(x,y);
        dfs(x,root);
    }
}
void add(int x,int pos){
    update(rt[x],0,n,0,pos);
    for(int i=x;fa[i];i=fa[i]){
        int Dep=Dis(x,fa[i]);
        update(rt[fa[i]],0,n,Dep,pos);
        update(rt[i+n],0,n,Dep,pos);
    }
}
int query(int x,int K){
    int res=Query(rt[x],0,n,K);
    for(int i=x;fa[i];i=fa[i]){
        int Dep=Dis(x,fa[i]);
        if(K-Dep<0)continue;
        res+=Query(rt[fa[i]],0,n,K-Dep);
        res-=Query(rt[i+n],0,n,K-Dep);
    }
    return res;
}
void clear(){
    for(int i=1;i<=tot;i++)
        lson[i]=rson[i]=sum[i]=0;
    tot=0;
    id=0;
    root=0;
    memset(rt,0,sizeof(rt));
    memset(vis,0,sizeof(vis));
    memset(head,0,sizeof(head));
}
int main(){
    while(scanf("%d%d",&n,&q)!=EOF){
        clear();
        for(int i=1;i<=n;i++)
            scanf("%d",&A[i]);
        for(int i=1;i<n;i++){
            scanf("%d%d",&x,&y);
            add_edge(x,y);
            add_edge(y,x);
        }
        dfs1(0,1);dfs2(1,0,1);
        Siz=n;dfs_root(0,1);dfs(0,root);
        for(int i=1;i<=n;i++)
            add(i,A[i]);
        while(q--){
            scanf("%s%d%d",&c,&x,&y);
            if(c=='?')printf("%d\n",query(x,y));
            else {
                add(x,y-A[x]);
                A[x]=y;
            }
        }
    }
    return 0;
}

技巧

  • 先想暴力,如果想到的暴力可以过二叉树,那么尝试套用点分治。

  • 考虑把每个点的信息用路径的方式来表达。(专题O题)

  • 学会活用点分治,不要硬套板子。(专题F题)

  • 想暴力尽量往 $O(n^2)$ 的地方想。(专题I题)每个节点不接受父亲的信息,每个节点都要遍历一次所有子树。