[图论] 点分治

· · 个人记录

点分治

一些定义

P3806 【模板】点分治1

题意

给你一棵 n 个点的无根树，每条边上都有一个权值，求长度不超过 k 的路径有多少条（距离为k 的路径是否存在）。

题解

树的重心求法

void find_rt(int u,int fa){
    sz[u]=1;mx[u]=0;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa || vis[v])continue;//vis数组之后分治要用到
        find_rt(v,u);
        sz[u]+=sz[v];
        Mx(mx[u],sz[v]);
    }
    Mx(mx[u],S-sz[u]);
    if(mx[u]<mx[rt])rt=u;//取mx尽量小的
}

我们在点分治过程中每次选取子树的重心为子树的树根进行处理， 这样总的递归深度不会超过 logN 层， 整个点分治的时间复杂度也就保证了O(NlogN)

例题题解

给定一棵有n个点的树。

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

此 .md 提供蓝书思想：

不难发现树上的路径分为两类：

  1. 经过根节点的路径

  2. 包含于子树的路径

对于前者，可以用 dis[u] 表示 u 到 root 的距离，u 到 v 的路径长即为 dis[u]+dis[v]

对于后者，递归处理（采用分治思想的体现）

点分治题的思想大都如上， 对于不同的题要设计不同的 calc 函数处理问题。

本题中，k 的规模过大，一般需要离线处理。

利用桶的思想，进行如下操作：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int read()
{
    int f=1,x=0;
    char ss=getchar();
    while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();}
    while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();}
    return f*x;
}
inline void CheckMax(int &x,int y){if(x<y)x=y;return ;}
const int maxn = 1e5 + 10 , INF = 1e8 + 10;
int head[maxn],cnt=0;
struct edge{
    int to,nxt,w;
}e[maxn<<1];
inline void link(int u,int v,int w){
    e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;e[cnt].w=w;
}
int sz[maxn],mx[maxn],rt,S;
bool vis[maxn];
void find_rt(int u,int fa){
    sz[u]=1;mx[u]=0;//多测清空
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(vis[v] || v==fa)continue;
        find_rt(v,u);
        sz[u]+=sz[v];
        CheckMax(mx[u],sz[v]);
    }
    CheckMax(mx[u],S-sz[u]);
    if(mx[u]<mx[rt])rt=u;//rt需要初始化为INF
}
int n,m;
int query[maxn],dis[maxn],rem[maxn],test[INF],que[maxn];
bool judge[INF];
void getdis(int u,int fa){
    rem[++rem[0]]=dis[u];
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa || vis[v])continue;
        dis[v]=dis[u]+e[i].w;
        getdis(v,u);
    }
}
void calc(int u){//没必要记录fa，u的fa肯定被标记上了
    int t=0;
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(vis[v])continue;
        rem[0]=0;dis[v]=e[i].w;
        getdis(v,u);//统计一棵子树
        for(int j=rem[0];j>=1;j--)
            for(int k=1;k<=m;k++)if(query[k]>=rem[j])test[k]|=judge[query[k]-rem[j]];
        for(int j=rem[0];j>=1;j--)judge[rem[j]]=true,que[++t]=rem[j];
    }
    for(int i=1;i<=t;i++)judge[que[i]]=false;
}
void solve(int u){
    vis[u]=true;judge[0]=true;//0肯定是可以满足的，否则在第一棵子树会wa
    calc(u);
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if(vis[v])continue;
        S=sz[v];mx[rt=0]=INF;
        find_rt(v,0);solve(rt);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,u,v,w;i<n;i++){
        scanf("%d%d%d",&u,&v,&w);
        link(u,v,w);link(v,u,w);
    }
    for(int i=1;i<=m;i++)query[i]=read();
    mx[rt]=INF;S=n;
    find_rt(1,0);
    solve(rt);
    for(int i=1;i<=m;i++){
        if(test[i])puts("AYE");
        else puts("NAY");
    }
    return 0;
}

注意桶开小会RE

几个细节