点分治

点分治(1·针对裸题)

luogu P3806 【模板】点分治1

题目描述

给定一棵有n个点的树
询问树上距离为k的点对是否存在。
输入格式:
n,m 接下来n-1条边a,b,c描述a到b有一条长度为c的路径
接下来m行每行询问一个K
输出格式:
对于每个K每行输出一个答案,存在输出“AYE”,否则输出”NAY”(不包含引号)

传送门

分析:

我们先定义一些变量:

int n,m,flag;
struct edge{int from,to,cost;}bian[N];
int head[N],tot,sum,root;//sum是子树的总点数,root为根。
int max_son[N],son[N];//max_son是子树的最大集,son为以i为根的子树节点。
bool vis[N],k_ans[100000010];//访问标记,k_ans为k是否存在。
int rode[N];//i到根的距离。
struct node {int ancestors,cost;}dian[N];//ancestors,表示点i除根以外的最浅祖先,cost表示到根的代价。

然后我们要往图里加入点:( 这非常简单)

void add(int l,int r,int k){bian[++tot]=(edge){head[l],r,k};head[l]=tot;}

然后我们要找重心,如果不利用重心对代码进行优化,复杂度可能变大,本蒟蒻就不解释了。找重心只要遍历整棵树,找到所有节点中儿子大小最大值最小的点就是重心,代码中用root表示。

void find_root(int now,int fa)//递归找重心。
{
    son[now]=1,max_son[now]=0;
    for(int i=head[now];i;i=bian[i].from)
    {
        int next=bian[i].to;
        if(vis[next]||next==fa)
            continue;
        find_root(next,now);
        son[now]+=son[next];
        max_son[now]=max(max_son[now],son[next]);
    }
    max_son[now]=max(max_son[now],sum-son[now]);
    if(max_son[now]<max_son[root])
        root=now;
}

然后,就到了整个代码的核心,点分治。我们已知暴力枚举长度,复杂度爆炸,然而,如果我们每次找到这棵树的重心,O(n)遍历棵树,找到每个节点到根的cost,最后暴利把两条位于不同子树的链组合起来,更新k ans数组就好了。接着就删去现在的根节点,找到剩下子树的重心,重复上面的操作就好了,复杂度大概是n logn^2
下面是完整代码:

#include<bits/stdc++.h>
using namespace std;
const LL N=2e4+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
namespace FastIO
{
    template inline void read(tp &x)
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x)
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
int n,m,flag;
struct edge{int from,to,cost;}bian[N];
int head[N],tot,sum,root;//sum是子树的总点数,root为根。
int max_son[N],son[N];//max_son是子树的最大集,son为以i为根的子树节点。
bool vis[N],k_ans[100000010];//访问标记,k_ans为k是否存在。
int rode[N];//i到根的距离。
struct node {int ancestors,cost;}dian[N];
void add(int l,int r,int k){bian[++tot]=(edge){head[l],r,k};head[l]=tot;}
void find_root(int now,int fa)//递归找重心。
{
    son[now]=1,max_son[now]=0;
    for(int i=head[now];i;i=bian[i].from)
    {
        int next=bian[i].to;
        if(vis[next]||next==fa)
            continue;
        find_root(next,now);
        son[now]+=son[next];
        max_son[now]=max(max_son[now],son[next]);
    }
    max_son[now]=max(max_son[now],sum-son[now]);
    if(max_son[now]<max_son[root])
        root=now;
}
int tot_anss;
void solve_dfs(int now,int zuxian,int fa)
{
    for(int i=head[now];i;i=bian[i].from)
    {
        int next=bian[i].to;
        if(vis[next]||fa==next)
            continue;
        rode[next]=rode[now]+bian[i].cost;
        dian[++tot_anss]=(node){zuxian,rode[next]};
        solve_dfs(next,zuxian,now);
    }
}
void find_k(int now)
{
    rode[now]=0,tot_anss=0;
    vis[now]=1;
    for(int i=head[now];i;i=bian[i].from)
    {
        int next=bian[i].to;
        if(vis[next]==1)
        continue;
        rode[next]=bian[i].cost;
        dian[++tot_anss]=(node){next,rode[next]};
        solve_dfs(bian[i].to,bian[i].to,now);
    }
    for (int i=1;i<=tot_anss;i++) k_ans[dian[i].cost]=1;
    for(int i=1;i<=tot_anss;i++)
        for(int j=i+1;j<=tot_anss;j++)
        if(dian[i].ancestors!=dian[j].ancestors)
            k_ans[dian[i].cost+dian[j].cost]=1;
    for(int i=head[now];i;i=bian[i].from)
    {
        int next=bian[i].to;
        if(!vis[next])
        {
            max_son[0]=inf;
            root=0;
            sum=son[next];
            find_root(next,0);
            find_k(root);
        }
    }
}
int main()
{
    read(n),read(m);
    for(int i=1;i<n;i++)
    {
        int l,r,k;
        read(l),read(r),read(k);
        add(l,r,k);add(r,l,k);
    }
    sum=max_son[0]=n,root=0;//root必须更新。
    find_root(1,0);
    find_k(root);
    for(int i=1;i<=m;i++)
    {
        read(flag);
        if(k_ans[flag]==1)
            printf("AYE\n");
        else
            printf("NAY\n");
    }
    return 0;
}

day2 luogu P2634 [国家集训队]聪聪可可

分析:

这道题就是在上题的模板上,把统计k改成%3就好了,所以k_ans数组就没用了,但刚开始,我边的数组开小了,所以wa了一发。
###代码如下:

#include<bits/stdc++.h>
using namespace std;
const LL N=2e4+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
namespace FastIO
{
    template inline void read(tp &x)
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template inline void write(tp x)
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template inline void writeln(tp x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
int n,m,flag;
struct edge{int from,to,cost;}bian[N*2];
int head[N],tot,sum,root;//sum是子树的总点数,root为根。
int max_son[N],son[N];//max_son是子树的最大集,son为以i为根的子树节点。
bool vis[N];//访问标记,k_ans为k是否存在。
int rode[N],ans;//i到根的距离。
struct node {int ancestors,cost;}dian[N];
inline void add(int l,int r,int k){bian[++tot]=(edge){head[l],r,k};head[l]=tot;}
inline void find_root(int now,int fa)//递归找重心。
{
    son[now]=1,max_son[now]=0;
    for(register int i=head[now];i;i=bian[i].from)
    {
        register int next=bian[i].to;
        if(vis[next]||next==fa)
            continue;
        find_root(next,now);
        son[now]+=son[next];
        max_son[now]=max(max_son[now],son[next]);
    }
    max_son[now]=max(max_son[now],sum-son[now]);
    if(max_son[now]<max_son[root])
        root=now;
}
int tot_anss;
inline void solve_dfs(int now,int zuxian,int fa)
{
    for(register int i=head[now];i;i=bian[i].from)
    {
        register int next=bian[i].to;
        if(vis[next]||fa==next)
            continue;
        rode[next]=rode[now]+bian[i].cost;
        dian[++tot_anss]=(node){zuxian,rode[next]};
        solve_dfs(next,zuxian,now);
    }
}
inline void find_k(int now)
{
    rode[now]=0,tot_anss=0;
    vis[now]=1;
    for(register int i=head[now];i;i=bian[i].from)
    {
        register int next=bian[i].to;
        if(vis[next]==1)
            continue;
        rode[next]=bian[i].cost;
        dian[++tot_anss]=(node){next,rode[next]};
        solve_dfs(bian[i].to,bian[i].to,now);
    }
    for (register int i=1;i<=tot_anss;i++) 
        if(dian[i].cost%3==0) 
            ans++;
    for(register int i=1;i<=tot_anss;i++)
        for(register int j=i+1;j<=tot_anss;j++)
            if(dian[i].ancestors!=dian[j].ancestors)
                if((dian[i].cost+dian[j].cost)%3==0)
                    ans++;
    for(register int i=head[now];i;i=bian[i].from)
    {
        register int next=bian[i].to;
        if(!vis[next])
        {
            max_son[0]=inf;
            root=0;
            sum=son[next];
            find_root(next,0);
            find_k(root);
        }
    }
}
main()
{
    read(n);
    for(register int i=1;i<n;i++)
    {
        register int l,r,k;
        read(l),read(r),read(k);
        add(l,r,k);add(r,l,k);
    }
    sum=max_son[0]=n,root=0;//root必须更新。
    find_root(1,0);
    find_k(root);
    int zz=n*n;
    ans*=2;
    ans+=n;
    int gcd=__gcd(zz,ans);
    printf("%d/%d\n",ans/gcd,zz/gcd);
    return 0;
}

好久没写博客了,如有错误,请留言。

关于“点分治”我的1个想法

发表评论

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