静态点分治总结

Author Avatar
rtrt 3月 14, 2025

归档于 2019-07-26 17:07

点分治是世界上最好的算法QwQ

点分治可以解决各种树上的边权点权问题，然后如果你发现这个题好像问的特别玄学，lca，树差都做不了，树上动‘龟’更做不了，只能暴力时，这个题大多数情况就是点分治了

点分治的思路，考虑指定p为根，对于p而言，树上路径分为两类，过p的路径，子树内的路径，显然对于子树内的路径，只要让他继续递归下去就行了，然后我们现在要算的就是经过p的路径

算法过程

一，求出来重心

二，从重心开始跑dfs维护出这一段权值（路径长度等）

三，运行calc计算对ans贡献

四，从子树运行一–三

点分治时间复杂度nlogn，证明被咕了

为什么非得是重心，首先复杂度与最大的子树有关，如果是直接往下搜y时，遇到一个链会退化成$n^2 log
n$，若从重心开始搜，保证了子树小于$\frac{n}{2}$

运行点分治大约有两种思路第一种是暴力计算然后容斥（为什么容斥被咕了），第二种是类似树形背包转移，再加上各种数据结构维护

两种都比较常用容斥特别好打，背包适用广

我们拿几个例题看看点分治的思路

例题

聪聪可可

一颗n(n<=20000)个点的树上,求长度是3的倍数的路径条数。

思路清真，我们统计出来各个子树内路径，最后让他们合并（长度余2与长度余1合并，长度余3于长度余3合并）最终就得到了解，我们维护出每一段路径的余数

类似于

void getdeep(ll x,ll fa){
    tt[deep[x]%3]++;
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(vis[y]||y==fa) continue;
        deep[y]=deep[x]+edge[i];
        getdeep(y,x);
    }
}
ll calc(ll x,ll val){
    deep[x]=val;
    for(ll i=0;i<=2;i++)
        tt[i]=0;
    getdeep(x,0);
    return tt[1]*tt[2]*2+tt[0]*tt[0];
} 


#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define Inf 1008611555ll
#define A 1000000
ll head[A],nxt[A],ver[A],edge[A],sz[A],vis[A],tt[A],deep[A];
ll size,toot,n,m,mx,ans,tot;
void add(ll x,ll y,ll z){
    nxt[++tot]=head[x],head[x]=tot,ver[tot]=y,edge[tot]=z;
}
ll gcd(ll x,ll y){
    if(y==0) return x;
    return gcd(y,x%y);
}
void gettoot(ll x,ll fa){
    sz[x]=1;ll num=0;
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(vis[y]||y==fa) continue;
        gettoot(y,x);
        sz[x]+=sz[y];
        num=max(num,sz[y]);
    }
    num=max(num,size-sz[x]);
    if(num<mx) mx=num,toot=x;
}
void getdeep(ll x,ll fa){
    tt[deep[x]%3]++;
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(vis[y]||y==fa) continue;
        deep[y]=deep[x]+edge[i];
        getdeep(y,x);
    }
}
ll calc(ll x,ll val){
    deep[x]=val;
    for(ll i=0;i<=2;i++)
        tt[i]=0;
    getdeep(x,0);
    return tt[1]*tt[2]*2+tt[0]*tt[0];
}
ll solve(ll x){
    ans+=calc(x,0);
//    printf("x=%lld t1=%lld t2=%lld t0=%lld ans=%lld\n",x,tt[1],tt[2],tt[0],ans);
    vis[x]=1;
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(vis[y]) continue;
        ans-=calc(y,edge[i]);
//        printf("ans=%lld\n",ans);
        size=sz[y];
        mx=Inf;
        gettoot(y,0);
        solve(toot);
    }
}
int main(){
    scanf("%lld",&n);
    for(ll i=1;i<n;i++){
        ll x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        add(x,y,z);add(y,x,z);
    }
    mx=Inf;
    size=n;
    gettoot(1,0);
    solve(toot);
    ll g=gcd(ans,n*n);
    printf("%lld/%lld\n",ans/g,n*n/g);
}

View Code

tree

给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K

思路清真，我们统计出来子树之间距离然后统计一波排序一波，点对一波就好了

类似于

void getdis(ll x,ll fa){
    q[++r]=d[x];
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(y==fa||vis[y]) continue;
        d[y]=d[x]+edge[i];
        getdis(y,x);
    }
}
ll calc(ll x,ll val){
    r=0;d[x]=val;
    getdis(x,0);
    ll sum=0;l=1;
    sort(q+1,q+r+1);
    while(l<r){
        if(q[l]+q[r]<=k) sum+=r-l,++l;
        else --r;
    }
    return sum;  
}  


#include<bits/stdc++.h>
#define ll long long
#define A 1100000
#define Inf 1000000000ll
using namespace std;
ll head[A],nxt[A],ver[A],sz[A],q[A],d[A],sum[A],edge[A];
ll size,toot,mx,n,m,tot=0,ans,k,l,r;
bool vis[A];
void add(ll x,ll y,ll z){
    ver[++tot]=y,nxt[tot]=head[x],head[x]=tot,edge[tot]=z;
}
void gettoot(ll x,ll fa){
    sz[x]=1;ll num=0;
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(y==fa||vis[y]) continue;
        gettoot(y,x);
        sz[x]+=sz[y];
        num=max(num,sz[y]);
    }
    num=max(size-sz[x],num);
    if(num<mx) mx=num,toot=x;
}
void getdis(ll x,ll fa){
    q[++r]=d[x];
//    printf("   x=%lld r=%lld\n",x,r);
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(y==fa||vis[y]) continue;
        d[y]=d[x]+edge[i];
        getdis(y,x);
    }
}
ll calc(ll x,ll val){
    r=0;d[x]=val;
    getdis(x,0);
    ll sum=0;l=1;
//    printf("r=%lld l=%lld\n",l,r);
    sort(q+1,q+r+1);
    while(l<r){
        if(q[l]+q[r]<=k) sum+=r-l,++l;
        else --r;
    }
    return sum;
}
ll solve(ll x){
    ans+=calc(x,0);
    vis[x]=1;
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(vis[y]) continue;
        ans-=calc(y,edge[i]);
        size=sz[y];
        mx=Inf;
        gettoot(y,0);
        solve(toot);
    }
}
int main(){
    scanf("%lld",&n);
    for(ll i=1;i<n;i++){
        ll x,y,z;
        scanf("%lld%lld%lld",&x,&y,&z);
        add(x,y,z);add(y,x,z);
    }
    scanf("%lld",&k);
    size=n;
    mx=Inf;
    gettoot(1,0);
    solve(toot);
    cout<<ans<<endl;
}

View Code

race

路径和为k且路径的边数最少

我们开一个桶，维护出路径和为k时边数最小值，记得清零

类似这样

void getdiss(ll x,ll fa,ll dp){
    if(deep[x]<=k)
        ans=min(ans,dp+cnt[k-deep[x]]);
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(vis[y]||y==fa) continue;
        deep[y]=deep[x]+edge[i];
        getdiss(y,x,dp+1);
    }
}
void uptoday(ll x,ll fa,ll dp,ll ooo){
    if(deep[x]<=k)
    ooo?(cnt[deep[x]]=min(cnt[deep[x]],dp)):cnt[deep[x]]=n;
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(vis[y]||y==fa) continue;
        uptoday(y,x,dp+1,ooo);
    }
}
void solve(ll x){
    vis[x]=1;cnt[0]=0;
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(vis[y]) continue;
        deep[y]=edge[i];
        getdiss(y,0,1);
        uptoday(y,0,1,1);
    }
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(!vis[y])
            uptoday(y,0,1,0);
    }
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(vis[y]) continue;
        mx=Inf;
        size=sz[y];
        gettoot(y,0);
        solve(toot);
    }
}


#include<bits/stdc++.h>
using namespace std;
#define ll int
#define Inf 1e9
#define A 6100000
ll t[A+10],sz[A],nxt[A],head[A],ver[A],edge[A],cnt[A],deep[A];
ll mx,size,num,k,toot,ans=0,n,tot=0;
bool vis[A];
void add(ll x,ll y,ll z){
    ver[++tot]=y,nxt[tot]=head[x],head[x]=tot,edge[tot]=z;
}
void gettoot(ll x,ll fa){
    sz[x]=1;ll num=0;
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(vis[y]||y==fa) continue;
        gettoot(y,x);
        sz[x]+=sz[y];
        num=max(num,sz[y]);
    }
    num=max(num,size-sz[x]);
    if(num<mx) mx=num,toot=x;
}
void getdiss(ll x,ll fa,ll dp){
    if(deep[x]<=k)
        ans=min(ans,dp+cnt[k-deep[x]]);
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(vis[y]||y==fa) continue;
        deep[y]=deep[x]+edge[i];
        getdiss(y,x,dp+1);
    }
}
void uptoday(ll x,ll fa,ll dp,ll ooo){
    if(deep[x]<=k)
    ooo?(cnt[deep[x]]=min(cnt[deep[x]],dp)):cnt[deep[x]]=n;
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(vis[y]||y==fa) continue;
        uptoday(y,x,dp+1,ooo);
    }
}
void solve(ll x){
    vis[x]=1;cnt[0]=0;
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(vis[y]) continue;
        deep[y]=edge[i];
        getdiss(y,0,1);
        uptoday(y,0,1,1);
    }
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(!vis[y])
            uptoday(y,0,1,0);
    }
    for(ll i=head[x];i;i=nxt[i]){
        ll y=ver[i];
        if(vis[y]) continue;
        mx=Inf;
        size=sz[y];
        gettoot(y,0);
        solve(toot);
    }
}
int main(){
    cin>>n>>k;
    ans=n;
    ll x,y,z;
    for(ll i=1;i<=n-1;i++){
        cin>>x>>y>>z;x++,y++;
        add(x,y,z);add(y,x,z);
    }
    mx=Inf;size=n;
    for(ll i=1;i<=k;i++) cnt[i]=n;
    gettoot(1,0);
    solve(toot);
    if(ans==n)
        puts("-1");
    else 
        printf("%d\n",ans);
}

View Code

常见题目

路径和等于或小于等于k的点对（路径条数）。例如tree

路径和为某个数的倍数。没遇到过，但也应该类似于聪聪可可

路径和为k且路径的边数最少。例如race，我们只要开一个桶记录一下路径为k时最小路径

路径和mod M后为某个值。例如聪聪可可

路径上经过不允许点的个数不超过某个值，且路径和最大。例如免费旅行

大多数题开一个桶i，表示距离为i的相关信息，有时我们也可以用一些高级数据结构（例如树状数组）进行一波维护。