首页 📚学习笔记

点分治

点分治通常用于大规模处理树上路径信息问题

P3806 【模板】点分治

首先考虑暴力做法:枚举LCA的点,然后搜索两个子树看是否有长度相加为k的点对,这样的时间复杂度是$\mathcal O (N^2)$

现在换一种思路,假设我们选取了一个点,那么树上的路径就分为两种情况:
1.经过当前根节点
2.不经过当前根节点

我们处理出情况1的的答案,然后递归分给子树继续处理

问题来了,怎么选择根能使得最终的时间复杂度可以接受呢

很显然,你每递归一次,所有的点都会被搜索一次,所以最终时间复杂度为$\mathcal O (N·h)$的,所以我们要尽可能使得分下去的子树规模小一点

看上面这个图,如果我们选$1$,剩下子树大小就为$5$,但是如果选择了$3$,就会递归操作两棵大小分别为$2,3$的子树,当这条链足够长,后者时间复杂度显然优于前者

很容易就能想到树的重心,我们选择一棵树的重心为根,做完操作后,找到剩下每棵子树的重心作为根继续操作,根据重心的性质,子树的大小不超过整颗大小的$\frac{1}{2}$,所以时间复杂度为$\mathcal O (N·\log N)$

剩下的暴力搞搞就完事儿了

#include<bits/stdc++.h>
using namespace std;
const int N=50010;
const int MAXN=10000010;
int root,n,m,cnt,tot;
int sz[N],mx[N];
int last[N],que[N],ok[N],q[N],vis[N],in[MAXN],dis[N],other[MAXN];
struct edge{
    int pre,to,w;
}e[N*2];
inline int read(){
    int f=1,x=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return f*x;
}
inline void add(int x,int y,int w){
    cnt++;
    e[cnt].pre=last[x];
    e[cnt].to=y;
    e[cnt].w=w;
    last[x]=cnt;
}
inline void chkmax(int &x,int y){
    if(y>x)x=y;return;
}
void find(int x,int fa){//找重心 
    sz[x]=1;mx[x]=0;
    for(int i=last[x];i;i=e[i].pre){
        int to=e[i].to;
        if(to==fa||vis[to])continue;
        find(to,x);
        sz[x]+=sz[to];
        chkmax(mx[x],sz[to]);
    }
    chkmax(mx[x],(tot-sz[x]));
    if(mx[x]<mx[root])root=x;//更新重心 
}
inline void getdis(int x,int fa){//以重心开始暴力搜索 
    if(dis[x]<=10000000)
        in[++in[0]]=dis[x];
    for(int i=last[x];i;i=e[i].pre){
        int to=e[i].to;
        int w=e[i].w;
        if(vis[to]||to==fa)continue;
        dis[to]=dis[x]+w;
        getdis(to,x);
    }
}
inline void calc(int x){//暴力查找答案 
    int top=0;
    for(int i=last[x];i;i=e[i].pre){
        int to=e[i].to,w=e[i].w;
        if(vis[to])continue;
        in[0]=0;
        dis[to]=w;
        getdis(to,x);
        for(int j=in[0];j;j--)
            for(int k=1;k<=m;k++){
                if(in[j]<=que[k]){
                    ok[k]|=other[que[k]-in[j]];
                }
                    
            }
        for(int j=in[0];j;j--)q[++top]=in[j],other[in[j]]=1;
    }
    for(int i=1;i<=top;i++)other[q[i]]=0;
}
inline void solve(int x){//找重心,统计答案,递归子树 
    vis[x]=1;calc(x);
    for(int i=last[x];i;i=e[i].pre){
        int to=e[i].to;
        if(vis[to])continue;
        tot=sz[to];
        root=0;
        find(to,0);
        solve(root);
    }
}
int main(){
    n=read(),m=read();
    for(int i=1;i<n;i++){
        int x=read(),y=read(),z=read();
        add(x,y,z);
        add(y,x,z);
    }
    for(int i=1;i<=m;i++)
        que[i]=read();
    other[0]=1;mx[0]=N;
    root=0;
    tot=n;//初始树的大小 
    find(1,0);
    solve(root);
    for(int i=1;i<=m;i++)
        if(ok[i])puts("AYE");
        else puts("NAY");
    return 0;
}



文章评论

目录