淀粉质(点分治) 学习笔记

什么是淀粉质点分治?

就是把分治搬到树上,以某个点为根,分别分治处理子树的答案,再计算子树与子树间的答案的玄学算法。

举个例子:
如何求出一颗树上距离为K且所经过的点最少的点对?

对于这种题,我们可以把某个点(一般为重心)作为根,然后对左右子树递归处理,先分别得出左右子树的答案,再求出横跨两个子树之间的点对的答案。


为什么要学淀粉质

对于上面那道题,如果我们用传统的暴力做法,最优的复杂度只能得到O(n2)的暴力枚举,但是如果我们用淀粉质来搞,我们就可以做到O(n∗logn)的复杂度(如果K很大的话,我们可能还得套个数据结构上去,复杂度就变成了O(n∗log2n)),我们就可以通过这类题目。


怎么淀粉质啊

正如我们刚刚说说的,淀粉质的实质是选出一个点,对其左右子树分治,再计算组合不同子树的答案。

所以说,我们在处理某颗子树之前,必须先选出来一个点作为这个子树的根。

我们选的这个点,对我们复杂度的影响极其巨大。
我们可以考虑选重心,重心就是指如果这个点做为根,其任意一颗子树大小均不会超过总点树的1/2。
如果我们每次对子树分治的时候,新选的根是重心,那我们的树的总层数一定不会超过logn层。
对于找重心,我们每次都做一遍dfs就好。

int GetSize(int now)
{
    t_vis[now]=true;
    size[now]=1;
    for(int i=0;i<int(e[now].size());i++)
        if(t_vis[e[now][i].to]==false and vis[e[now][i].to]==false)
            size[now]+=GetSize(e[now][i].to);
    t_vis[now]=false;
    return size[now];
}
int root,cnt;
void GetRoot(int now)
{
    t_vis[now]=true;
    int t_size=1,OK=true;
    for(int i=0;i<int(e[now].size());i++)
        if(t_vis[e[now][i].to]==false and vis[e[now][i].to]==false)
        {
            GetRoot(e[now][i].to);
            if(size[e[now][i].to]>cnt/2) OK=false;
            t_size+=size[e[now][i].to];
        }
    if(cnt-t_size>cnt/2) OK=false;
    if(OK==true) root=now;
    t_vis[now]=false;
}

选出来重心之后,我们就可以以重心为根分治了。
首先,我们显然可以递归处理子树,然后再处理跨越两个子树的情况。
对于我们上面讲的那道题,我们所需要求的就是跨过两个子树且距离为K的点对的数量。
我们可以考虑这样做:
我们先开一个桶来记录长度为x的路径的点的数量,然后对每颗子树先做两遍dfs,第一遍先去桶里找到目前的点为止,之前找到的子树中有没有K-dis_now的路径。第二遍我们再把到每个点的距离放到桶里面去。
搞完之后,我们可以再dfs一次来回溯掉之前加上的东西,如果我们直接memset的话,会T的。
注意:我们这里的dfs必须只能走已经分治完成的点,分治完成的点才是其儿子

void dfs2(int now,int dis,int t_cnt,int type)
{
    t_vis[now]=true;
    if(type==1 and K-dis>=0)
        ans=min(ans,t_cnt+tot[K-dis]);
    if(type==2 and dis<M)
        tot[dis]=min(tot[dis],t_cnt);
    if(type==3 and dis<M)
        tot[dis]=inf;
    for(int i=0;i<int(e[now].size());i++)
        if(done[e[now][i].to]==true and t_vis[e[now][i].to]==false)
            dfs2(e[now][i].to,dis+e[now][i].w,t_cnt+1,type);
    t_vis[now]=false;
}
void dfs(int now)
{
    vis[now]=true;
    vector <road> son;
    son.reserve(32);
    for(int i=0;i<int(e[now].size());i++)
        if(vis[e[now][i].to]==false)
        {
            cnt=GetSize(e[now][i].to);
            GetRoot(e[now][i].to);
            dfs(root);
            son.push_back(e[now][i]);
        }
    for(int i=0;i<int(son.size());i++)
        dfs2(son[i].to,son[i].w,1,1),dfs2(son[i].to,son[i].w,1,2);
    for(int i=0;i<int(son.size());i++)
        dfs2(son[i].to,son[i].w,1,3);
    done[now]=true;
}

这样子搞,看起来时间复杂度很爆炸,其实并不大,因为我们最多有logn层,每层做n次,总复杂度也就只有O(n∗logn)

这样子,我们就搞定啦φ(>ω<*)


完整的代码

题目传送门:https://www.luogu.org/problemnew/show/P4149(题目稍有变动,但方法类似)

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
long long read()
{
    long long x=0,f=1; char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int N=200000+100;
const int M=1000000+100;
const int inf=0x3f3f3f3f;
struct road
{
    int to,w;
    road (int A,int B)
    {
        to=A,w=B;
    }
};
vector <road> e[N];
int n,K;
bool vis[N],t_vis[N],done[N];
int size[N],cnt,root;
int GetSize(int now)
{
    t_vis[now]=true;
    size[now]=1;
    for(int i=0;i<int(e[now].size());i++)
        if(t_vis[e[now][i].to]==false and vis[e[now][i].to]==false)
            size[now]+=GetSize(e[now][i].to);
    t_vis[now]=false;
    return size[now];
}
void GetRoot(int now)
{
    t_vis[now]=true;
    int t_size=1,OK=true;
    for(int i=0;i<int(e[now].size());i++)
        if(t_vis[e[now][i].to]==false and vis[e[now][i].to]==false)
        {
            GetRoot(e[now][i].to);
            t_size+=size[e[now][i].to];
            if(size[e[now][i].to]>(cnt/2))
                OK=false;
        }
    if(cnt-t_size>(cnt/2))
        OK=false;
    if(OK==true) root=now;
    t_vis[now]=false;
}
int ans=inf,tot[M];
void dfs2(int now,int dis,int t_cnt,int type)
{
    t_vis[now]=true;
    if(type==1 and K-dis>=0)
        ans=min(ans,t_cnt+tot[K-dis]);
    if(type==2 and dis<M)
        tot[dis]=min(tot[dis],t_cnt);
    if(type==3 and dis<M)
        tot[dis]=inf;
    for(int i=0;i<int(e[now].size());i++)
        if(done[e[now][i].to]==true and t_vis[e[now][i].to]==false)
            dfs2(e[now][i].to,dis+e[now][i].w,t_cnt+1,type);
    t_vis[now]=false;
}
void dfs(int now)
{
    vis[now]=true;
    vector <road> son;
    son.reserve(32);
    for(int i=0;i<int(e[now].size());i++)
        if(vis[e[now][i].to]==false)
        {
            cnt=GetSize(e[now][i].to);
            GetRoot(e[now][i].to);
            dfs(root);
            son.push_back(e[now][i]);
        }
    for(int i=0;i<int(son.size());i++)
        dfs2(son[i].to,son[i].w,1,1),dfs2(son[i].to,son[i].w,1,2);
    for(int i=0;i<int(son.size());i++)
        dfs2(son[i].to,son[i].w,1,3);
    done[now]=true;
}
int main()
{
    n=read(),K=read();
    for(int i=1;i<n;i++)
    {
        int s=read(),t=read(),w=read();
        e[s].push_back(road(t,w));
        e[t].push_back(road(s,w));
    }

    cnt=GetSize(1);
    GetRoot(1);
    memset(tot,0x3f,sizeof tot);
    tot[0]=0;
    dfs(root);

    if(ans>N) ans=-1;
    printf("%d",ans);
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注