【博客】点分治学习笔记

---戳这里原博客食用---

不要脸的推荐一波游记ZJOI2019游记：https://ac.nowcoder.com/discuss/175356

这里就不讲点分治的原理以及一些注意事项了，只讲几道例题吧（懒

[T1 Luogu3806]【模板】点分治1

给定一棵有n个点的树

询问树上距离为k的点对是否存在。

一看标题就是点分治了嘛...

这是之前在机房打的

对每个路径长度进行标记即可，考虑到重复标记，容斥原理搞一下对于子树的答案贡献权值-1即可（就是更新的时候把新增贡献改为-1）

 #include<cstdio>
#include<queue>
#include<iostream>
#include<cstring>
#define R register 
using namespace std;
inline int read(){
    int ans=0,f=1;char chr=getchar();
    while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
    while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
    return ans*f;
}const int M=100005<<1;
int head[M],ver[M],nxt[M],val[M],tot,n,m,x,root,sz[M],mx[M],vis[M],ANS[M],p,a[M],dis[M],s;
inline void add(int x,int y,int z){ver[++tot]=y;val[tot]=z;nxt[tot]=head[x];head[x]=tot;}
void Find_Gf(int x,int fa){//找根(请自动无视后面的GF)
    sz[x]=1;mx[x]=0;
    for(R int i=head[x];i;i=nxt[i])
        if(ver[i]!=fa&&!vis[ver[i]])
            Find_Gf(ver[i],x),sz[x]+=sz[ver[i]],mx[x]=max(mx[x],sz[ver[i]]);
    mx[x]=max(s-sz[x],mx[x]);
    if(mx[x]<mx[root]) root=x;
}
void dfs(int x,int len,int fa){//找路径
    dis[++p]=a[x];
    for(R int i=head[x];i;i=nxt[i])
        if(ver[i]!=fa&&!vis[ver[i]])
            a[ver[i]]=len+val[i],dfs(ver[i],a[ver[i]],x);
}
void Calc(int x,int len,int w){//标记路径
    p=0,a[x]=len,dfs(x,len,0);
    for(R int i=1;i<=p;++i)
        for(R int j=1;j<=p;++j)
            if(i!=j)    ANS[dis[i]+dis[j]]+=w;
}
void Solve(int x){//点分治
    Calc(x,0,1),vis[x]=1;
    for(R int i=head[x];i;i=nxt[i])
        if(!vis[ver[i]])
            Calc(ver[i],val[i],-1),s=sz[x],root=0,mx[0]=n,Find_Gf(ver[i],x),Solve(root);
}int main(){
    n=read();m=read();
    for(R int i=1,a,b,z;i<n;++i)
        a=read(),b=read(),z=read(),add(a,b,z),add(b,a,z);
    s=n,mx[0]=n,root=0;
    Find_Gf(1,0),Solve(root);
    while(m--)    puts(ANS[x=read()]?"AYE":"NAY");
    return 0;
}

[T2 Luogu2634] [国家集训队]聪聪可可

给定一棵树，求树上路径是3的倍数的条数

看到树上路径联想到点分

显然我们不可能开一个桶存边...观察发现只要记录下边权对3取模的结果就好了

并且对一个点来说，它的子树的贡献是这样的：

$ANS=cnt[1]*cnt[2]*2+{cnt[0]}^2$

考虑排除重复计算，在处理子树的子树时减掉即可，模板题

总数显然就是树上随便两个点并且可以重复所以就是${n}^2$

关于答案...除一个gcd就好了

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int M=100005<<1;
int head[M],ver[M],nxt[M],tot,val[M],n,m,s,vis[M],sz[M],mx[M],root,ans,cnt[M];
inline void add(int x,int y,int z){ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;val[tot]=z;}
inline int read(){
    int ans=0,f=1;char chr=getchar();
    while(!isdigit(chr)){chr=getchar();}
    while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
    return ans;
}
inline void cmax(int &x,int y){if(x<y)x=y;}
void find_gf(int x,int fa){
    mx[x]=sz[x]=1;
    for(int i=head[x];i;i=nxt[i]){
        if(vis[ver[i]]||ver[i]==fa) continue;
        find_gf(ver[i],x);
        cmax(mx[x],sz[ver[i]]);
        sz[x]+=sz[ver[i]];
    }cmax(mx[x],s-sz[x]);
    if(mx[root]>mx[x]) root=x;
}
void dfs(int x,int fa,int dis){
    ++cnt[dis%3];
    for(int i=head[x];i;i=nxt[i]){
        if(ver[i]==fa||vis[ver[i]]) continue;
        dfs(ver[i],x,(dis+val[i]%3));
    }
}
int Solve(int x,int w){
    cnt[0]=cnt[1]=cnt[2]=0;
    dfs(x,0,w);
    return cnt[1]*cnt[2]*2+cnt[0]*cnt[0];
}
void Divide(int x){
    ans+=Solve(x,0);
    vis[x]=1;
    for(int i=head[x];i;i=nxt[i]){
        if(vis[ver[i]]) continue;
        ans-=Solve(ver[i],val[i]);
        root=0,s=sz[ver[i]];mx[ver[i]]=1;
        find_gf(ver[i],0);Divide(root);
    }
}
signed main(){
    n=read();
    for(int i=1,x,y,z;i<n;++i){
        x=read(),y=read(),z=read();z%=3;
        add(x,y,z),add(y,x,z);
    }
    root=0,s=n;mx[root]=0x3f3f3f3f;
    find_gf(1,0);
    Divide(root);
    printf("%lld/%lld",ans/__gcd(ans,n*n),n*n/__gcd(ans,n*n));
    return 0;
}

T3 CF161D Distance in Tree

求一棵树上边权值和为k的条数

显然淀粉质无疑了...

先考虑权值小于等于K的条数，减去小于等于K-1的条数即可

在计算贡献的时候我们显然不可能双重循环寻找答案，时间复杂度会退化成O(${n}^2$$logn$),这样不如暴力+LCA求解方便快捷

其实这里面是含有一个单调性的

在点分的dfs过程中记录点到root的距离（用一个数组存储）,然后sort这个数组，O（n）扫描即可

时间复杂度O(n${log}^2$n),在可以承受的范围内（还有一些人直接把其中一个logn当常数来看了非严格来讲O($nlogn$)也不算错，毕竟logn最大也只有20不到）

这题还有一个双倍经验（Luogu P4178 Tree）

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define int long long
using namespace std;
const int M=100005<<1;
int head[M],ver[M],nxt[M],tot,val[M],n,m,s,vis[M],sz[M],mx[M],root,ans,a[M];
inline void add(int x,int y,int z){ver[++tot]=y;nxt[tot]=head[x];head[x]=tot;val[tot]=z;}
inline int read(){
    int ans=0,f=1;char chr=getchar();
    while(!isdigit(chr)){chr=getchar();}
    while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
    return ans;
}
inline void cmax(int &x,int y){if(x<y)x=y;}
void find_gf(int x,int fa){
    mx[x]=sz[x]=1;
    for(int i=head[x];i;i=nxt[i]){
        if(vis[ver[i]]||ver[i]==fa) continue;
        find_gf(ver[i],x);
        cmax(mx[x],sz[ver[i]]);
        sz[x]+=sz[ver[i]];
    }cmax(mx[x],s-sz[x]);
    if(mx[root]>mx[x]) root=x;
}
int p;
void dfs(int x,int fa,int dis){
    a[++p]=dis;
    for(int i=head[x];i;i=nxt[i]){
        if(ver[i]==fa||vis[ver[i]]) continue;
        dfs(ver[i],x,dis+1);
    }
}
int Solve(int x,int w){
    p=0;dfs(x,0,w);
    sort(a+1,a+p+1);
    int l=1,r=p,ans=0; 
    while(l<r)    if(a[l]+a[r]<=m)ans+=r-l,l++;    else r--;//计算<=k的
    l=1,r=p;
    while(l<r)     if(a[l]+a[r]<m)ans-=r-l,l++;    else r--;//计算<=k-1的
    return ans;
}
void Divide(int x){
    ans+=Solve(x,0);
    vis[x]=1;
    for(int i=head[x];i;i=nxt[i]){
        if(vis[ver[i]]) continue;
        ans-=Solve(ver[i],val[i]);
        root=0,s=sz[ver[i]];mx[ver[i]]=1;
        find_gf(ver[i],0);Divide(root);
    }
}
signed main(){
    n=read();m=read();
    for(int i=1,x,y,z;i<n;++i){
        x=read(),y=read(),z=1;
        add(x,y,z),add(y,x,z);
    }
    root=0,s=n;mx[root]=0x3f3f3f3f;
    find_gf(1,0);
    Divide(root);
    cout<<ans;
    return 0;
}

[T4 LuoguP4149] [IOI2011]Race

求一棵树上权值为K且覆盖边数最少的路径

就是把上面的问题结合一下，然后观察到K不是很大...

注意一点当前边权大于K的时候及时退出...不然桶会炸

#include<cstdio>
#include<queue>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read(){
    int ans=0,f=1;char chr=getchar();
    while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
    while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
    return ans*f;
}const int M=200005;
int n,kk,head[M<<1],ver[M<<1],nxt[M<<1],val[M<<1],tot,mx[M],vis[M],sz[M],root,s,Ans,dep[M],dis[M],p,b[1000100];
inline void add(int x,int y,int z){ver[++tot]=y;val[tot]=z;nxt[tot]=head[x];head[x]=tot;}
void Find_GF(int x,int fa){
    sz[x]=1,mx[x]=0;
    for(register int i=head[x];i;i=nxt[i]){
        if(vis[ver[i]]||ver[i]==fa) continue;
        Find_GF(ver[i],x);
        sz[x]+=sz[ver[i]],mx[x]=max(mx[x],sz[ver[i]]);
    }mx[x]=max(mx[x],s-sz[x]);
    if(mx[x]<mx[root]) root=x;
}
void DFS(int x,int fa,int d1,int d2){
    if(d1>kk) return;
    dis[++p]=d1;dep[p]=d2;
    for(register int i=head[x];i;i=nxt[i]){
        if(ver[i]==fa || vis[ver[i]]) continue;
        DFS(ver[i],x,d1+val[i],d2+1);
    }
}
inline void Calc(int x){
    b[0]=0,p=0;
    for(register int i=head[x];i;i=nxt[i]){
        if(vis[ver[i]]) continue;
        int lst=p;
        DFS(ver[i],x,val[i],1);
        for(register int j=lst+1;j<=p;++j)
            Ans=min(Ans,b[kk-dis[j]]+dep[j]);
        for(register int j=lst+1;j<=p;++j)
            b[dis[j]]=min(b[dis[j]],dep[j]);
    }for(int i=1;i<=p;i++) b[dis[i]]=1e9;
}
void Divide(int x){
    vis[x]=1,Calc(x);
    for(register int i=head[x];i;i=nxt[i]){
        if(vis[ver[i]]) continue;
        root=0,s=sz[ver[i]];root=0;
        Find_GF(ver[i],x);
        Divide(root);
    }
} 
int main(){Ans=0x3f3f3f3f;
    n=read(),kk=read();
    for(register int x,y,z,i=1;i<n;++i){
        x=read(),y=read(),z=read();++x,++y;
        add(x,y,z),add(y,x,z);
    }mx[0]=n+1,root=0,s=n;memset(b,0x3f,sizeof(b));
    Find_GF(1,0);
    Divide(root);
    if(Ans>=n)puts("-1");
    else printf("%d",Ans);
    return 0;
}

[T5 LuoguP4886]快递员

题目大意：

给定一棵n个节点的树和m个点对，在树上求一点使这个点到一个点对中每个点的距离之和的最大值的最小值...

见guai了...一眼看到根本没想到是点分治（然鹅打起来也不太像点分治...)看了一些大佬的题解才知道

我们随便找一个点比如重心，以其为根节点的儿子节点向外扩展（DFS），记录到每个节点的距离dis[]、它的祖先（根节点的某一个儿子）rt[]...

然后每个点对更新一下maxn值...并且记录那些点对可以取到maxn值...显然由于我们在模拟点分的过程...如果两个满足条件的点对却不连在同一个祖先（rt[]）上也是要舍掉的...

注意这里的DFS过程中不像其他点分治过程一样不能访问已经vis[]过的点，因为在遍历的过程中是要记录每一个节点在当前情况下的距离的！！

如果在某一个情况下访问到了已经访问过的节点只能说明所有情况都访问过了...可以直接输出退出了

#include<cstdio>
#include<queue>
#include<iostream>
#include<cstring>
#define R register  
#define GO(i) for(R int i=head[x];i;i=nxt[i])
using namespace std;
inline int read(){
    int ans=0,f=1;char chr=getchar();
    while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
    while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
    return ans*f;
}const int M=1e5+5;
int head[M<<1],ver[M<<1],nxt[M<<1],val[M<<1],tot,n,m,p[M],sz[M],mx[M],vis[M],s,root,px[M],py[M],rt[M],dis[M],Ans;
inline void add(int x,int y,int z){ver[++tot]=y;val[tot]=z;nxt[tot]=head[x];head[x]=tot;}
inline void cmax(int &x,int y){if(x<y) x=y;}
inline void cmin(int &x,int y){if(x>y) x=y;}
void Find_GF(int x,int fa){
    sz[x]=1,mx[x]=0;
    GO(i){
        if(ver[i]==fa||vis[ver[i]]) continue;
        Find_GF(ver[i],x);
        sz[x]+=sz[ver[i]],cmax(mx[x],sz[ver[i]]);
    }cmax(mx[x],s-sz[x]);
    if(mx[root]>mx[x]) root=x;
}
void DFS(int x,int fa,int root){
    rt[x]=root;
    GO(i){
        if(ver[i]==fa) continue;
        dis[ver[i]]=dis[x]+val[i];
        DFS(ver[i],x,root);
    }
}
void Divide(int x){
    if(vis[x]){cout<<Ans;exit(0);}
    vis[x]=1,dis[x]=0;
    GO(i)dis[ver[i]]=val[i],DFS(ver[i],x,ver[i]);
    int maxn=0,siz=0,lst=0;
    for(R int i=1;i<=m;++i)
        if(dis[px[i]]+dis[py[i]]>maxn)
             maxn=dis[px[i]]+dis[py[i]],p[siz=1]=i;
        else if(dis[px[i]]+dis[py[i]]==maxn) p[++siz]=i;
    cmin(Ans,maxn);
    for(R int i=1;i<=siz;++i){
        if(rt[px[p[i]]]!=rt[py[p[i]]]){cout<<Ans;exit(0);}
        else if(!lst) lst=rt[px[p[i]]];else if(lst!=rt[px[p[i]]]){cout<<Ans;exit(0);}
    }root=0;s=sz[lst];
    Find_GF(lst,x);Divide(root);
}
int main(){Ans=0x7fffffff;
    n=read(),m=read();
    for(R int i=1,x,y,z;i<n;++i){
        x=read(),y=read(),z=read();
        add(x,y,z),add(y,x,z);
    }root=0,s=n,mx[0]=0x3f3f3f3f;
    for(R int i=1;i<=m;++i) px[i]=read(),py[i]=read();
    Find_GF(1,0);Divide(root);
    return 0;
}

[UPD4.09]

然而并没有咕...不过是最后一次更新这篇啦