点分治复习笔记

1.Tree

Description:

求一棵树中长度不超过\(K\)的路径条数

Solution:

直接统计深度,由于深度的贡献具有单调性

考虑每次统计答案时先排序,然后双指针每次相减

这样就比\(n^2\)统计优秀多了,记得要减掉算重的

2.[模版]点分治1

Description:

求一棵树中是否存在长度为\(K\)的链,\(m\)组询问,\(m \le 100\)

Solution:

考虑每次用桶把路径长度标记,把所有询问在桶里查一遍,再清空桶

复杂度\(O(nmlog^2n)\)

#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ls p<<1 
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int mxn=1e5+5,inf=1e7;
int n,m,s,rt,cnt,tot,sumsz,f[mxn],hd[mxn],sz[mxn],vis[mxn],dis[mxn],ask[mxn],ans[mxn],tag[mxn],dep[mxn],bac[inf+5];

inline int read() {
    char c=getchar(); int x=0,f=1;
    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
    while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
    return x*f;
}
inline void chkmax(int &x,int y) {if(x<y) x=y;}
inline void chkmin(int &x,int y) {if(x>y) x=y;}

struct ed {
    int to,nxt,w;
}t[mxn<<1];

inline void add(int u,int v,int w) {
    t[++cnt]=(ed) {v,hd[u],w}; hd[u]=cnt;
}

int getrt(int u,int fa) {
    sz[u]=1; f[u]=0;
    for(int i=hd[u];i;i=t[i].nxt) {
        int v=t[i].to;
        if(v==fa||vis[v]) continue ;
        getrt(v,u); sz[u]+=sz[v];
        chkmax(f[u],sz[v]);
    }
    chkmax(f[u],sumsz-sz[u]);
    if(f[u]<f[rt]) rt=u;
}

void getdis(int u,int fa) {
    dis[++tot]=dep[u];
    for(int i=hd[u];i;i=t[i].nxt) {
        int v=t[i].to;
        if(v==fa||vis[v]) continue ;
        dep[v]=dep[u]+t[i].w; getdis(v,u); 
    }
}

void cal(int u) {
    s=0;
    for(int i=hd[u];i;i=t[i].nxt) {
        int v=t[i].to;
        if(vis[v]) continue ;
        dep[v]=t[i].w; tot=0; getdis(v,u);
        for(int j=1;j<=m;++j) {
            for(int k=1;k<=tot;++k) {
                if(dis[k]>ask[j]) break ;
                ans[j]|=bac[ask[j]-dis[k]];
            }
        }
        for(int k=1;k<=tot;++k) 
            if(dis[k]<=inf) bac[dis[k]]=1,tag[++s]=dis[k];
    }
    for(int i=1;i<=s;++i) bac[tag[i]]=0; bac[0]=1;
}

void solve(int u) {
    vis[u]=1; cal(u); 
    for(int i=hd[u];i;i=t[i].nxt) {
        int v=t[i].to;
        if(vis[v]) continue ;
        sumsz=sz[v]; rt=0; 
        getrt(v,u); solve(rt);
    }
}

int main()
{
    n=read(); m=read(); int u,v,w; bac[0]=1; 
    for(int i=1;i<n;++i) {
        u=read(); v=read(); w=read();
        add(u,v,w); add(v,u,w);
    }
    for(int i=1;i<=m;++i) ask[i]=read();
    rt=0; sumsz=f[0]=n; getrt(1,0); solve(rt);
    for(int i=1;i<=m;++i) 
        if(ans[i]) puts("AYE"); else puts("NAY");
    return 0;
}

3.聪聪可可

Description:

给你一棵树,询问有多少条路径满足边权和为3的倍数

Solution:

和Tree差不多......统计时开3个桶,乘法原理搞一下就行

4.Distance in Tree

Description:

给你一棵树,问路径长为K的条数

Solution:

方法同2,如果你无聊的话可以写个类似Tree的写法用<=k的减去<k的

#include <map>
#include <set>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define ls p<<1 
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int mxn=1e5+5;
int n,m,k,rt,cnt,tot,ans,sumsz,f[mxn],hd[mxn],sz[mxn],bac[mxn],dep[mxn],vis[mxn],dis[mxn];

inline int read() {
    char c=getchar(); int x=0,f=1;
    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
    while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
    return x*f;
}
inline void chkmax(register int &x,register int y) {if(x<y) x=y;}
inline void chkmin(register int &x,register int y) {if(x>y) x=y;}

struct ed {
    int to,nxt,w;
}t[mxn<<1];

inline void add(register int u,register int v,register int w) {
    t[++cnt]=(ed) {v,hd[u],w}; hd[u]=cnt;
}

int getrt(register int u,register int fa) {
    f[u]=0; sz[u]=1;
    for(register int i=hd[u];i;i=t[i].nxt) {
        register int v=t[i].to;
        if(v==fa||vis[v]) continue ;
        getrt(v,u); sz[u]+=sz[v];
        chkmax(f[u],sz[v]);
    }
    chkmax(f[u],sumsz-sz[u]);
    if(f[rt]>f[u]) rt=u;
}

void getdis(register int u,register int fa) {
    if(dep[u]<=k) ++dis[dep[u]],ans+=bac[k-dep[u]];
    for(register int i=hd[u];i;i=t[i].nxt) {
        register int v=t[i].to;
        if(v==fa||vis[v]) continue ;
        dep[v]=dep[u]+t[i].w; getdis(v,u); 
    }
}

void cal(register int u) {
    tot=0; 
    for(register int i=hd[u];i;i=t[i].nxt) {
        register int v=t[i].to;
        if(vis[v]) continue ;
        dep[v]=t[i].w; getdis(v,u);
        for(register int j=1;j<=k;++j) 
            bac[j]+=dis[j],dis[j]=0;
    }
    for(register int i=1;i<=k;++i) bac[i]=0;
}

void solve(register int u) {
    cal(u); vis[u]=1;
    for(register int i=hd[u];i;i=t[i].nxt) {
        register int v=t[i].to;
        if(vis[v]) continue ;
        rt=0; sumsz=sz[v];
        getrt(v,u); solve(rt);
    }
}

int main()
{
    n=read(); k=read(); register int u,v,w; bac[0]=1;
    for(register int i=1;i<n;++i) {
        u=read(); v=read(); w=1;
        add(u,v,w); add(v,u,w);
    }
    rt=0; sumsz=f[0]=n;
    getrt(1,0); solve(rt);
    printf("%d",ans);
    return 0;
}

点分治复习笔记

原文：https://www.cnblogs.com/list1/p/10621210.html