luogu P4183 Cow at Large P （暴力吊打点分治）(内有时间复杂度证明）

题面

贝茜被农民们逼进了一个偏僻的农场。农场可视为一棵有N个结点的树，结点分别编号为 1,2,…,N 。每个叶子结点都是出入口。开始时，每个出入口都可以放一个农民（也可以不放）。每个时刻，贝茜和农民都可以移动到相邻的一个结点。如果某一时刻农民与贝茜相遇了（在边上或点上均算），则贝茜将被抓住。抓捕过程中，农民们与贝茜均知道对方在哪个结点。

请问：对于结点 i$(1\leq i\leq N)$，如果开始时贝茜在该结点，最少有多少农民，她才会被抓住。

分析

先考虑问题的简化版，对于给定的起点s求出答案

设dist(x,y)表示x,y两点之间的距离

我们发现，对于某一个节点x,若$dist(s,x) \geq \min {dist(x,u) } $ 其中u为x的子树中的叶子节点，那么从x走到s的时

候就会被抓住.$\min {dist(x,u) } $可以通过一次BFS预处理出来

显然奶牛越早被抓住更好，从节点s出发DFS，只要当前节点x满足上述条件，则ans++,并不访问x子树中的节点。因为如果在x点被抓住了，它就不会到比x深度更大的节点去了

这样的复杂度显然是$O(n^2)$

有一个玄学优化，可以通过此题，方法如下

1.DP一遍求出每个点到最近的叶子节点的距离dp[x]

2.DFS，把链缩成一条边，因为可以发现不管在链的哪里拦截都是一样的

3.每次暴力，当dp[x]<=dist(x,root)的时候ans++,return

可以证明把链缩掉之后是$O(n\sqrt{n})$的

由于没有链，我们可以把模型简化为一个满k叉树(k>1)，每次暴力DFS，显然DFS的深度不超过树的深度的1/2，即$O(log_kn)$

访问的子树大小为

\[1+k+k^2+...+k^{\frac{1}{2}\log_kn}=\frac{k^{(\frac{1}{2}\log_kn)+1}-1}{k-1}=\frac{k^{\log_kn} \times \sqrt k-1}{k-1}=\frac{k\sqrt{n}-1}{k-1}=\sqrt{n}+\frac{\sqrt{n}-1}{k-1}
\]

显然当k=2最大，为$2\sqrt{n}-1$,

所以总时间复杂度为$O(n\sqrt{n})$,与分块相同,且常数远小于点分治

代码

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#define maxn 100005

#define INF 0x3f3f3f3f

using namespace std;

inline void qread(int &x){

    x=0;

     char c=getchar();

    while(c<'0'||c>'9'){

        c=getchar();

    }

    while(c>='0'&&c<='9'){

        x=x*10+c-'0';

        c=getchar();

    }

}

inline void qprint(int x){

    if(x==0){

        putchar('0');

        return;

    }else{

        if(x>=10) qprint(x/10);

        putchar(x%10+'0');

    }

}

int n,k;

struct edge{

    int from;

    int to;

    int next;

    int nfrom;

    int nto;

    int len;

}E[maxn<<1];

int head[maxn];

int deg[maxn];

int sz=1;

void add_edge(int u,int v){

    deg[u]++;

    deg[v]++;

    sz++;

    E[sz].from=u;

    E[sz].to=v;

    E[sz].next=head[u];

    head[u]=sz;

}

int dp[maxn];//表示离x最近的叶子节点到x的距离

//不能从一个根开始DFS，因为此时根不定，

//到一个点最近的叶子节点不一定在DFS时的子树里，而可能在它上方 

void bfs(){

    queue<int>q;

    for(int i=1;i<=n;i++){

        if(deg[i]<=1){

            q.push(i);

            dp[i]=0;

        }else dp[i]=INF;

    }

    while(!q.empty()){

        int x=q.front();

        q.pop();

        for(int i=head[x];i;i=E[i].next){

            int y=E[i].to;

            if(dp[y]==INF){

                dp[y]=min(dp[y],dp[x]+1);

                q.push(y);

            }

        }

    }

}

int s,t,d;

void dfs2(int x,int fa,int deep){

    if(fa!=0&&deg[x]!=2){

        s=x;

        t=fa;

        d=deep;

        return;

    }

    for(int i=head[x];i;i=E[i].next){

        int y=E[i].to;

        if(y!=fa){

            dfs2(y,x,deep+1);

            E[i].nto=s;

            E[i].nfrom=t;

            E[i].len=d-deep;

        }

    }

}

int ans=0;

void dfs3(int x,int fa,int deep){

    if(deep>=dp[x]){

        ans++;

        return;

    }

    for(int i=head[x];i;i=E[i].next){

        int y=E[i].to;

        if(y!=fa){

            dfs3(E[i].nto,E[i].nfrom,deep+E[i].len);

        }

    }

}

int main(){

    int u,v;

    qread(n);

    for(int i=1;i<n;i++){

        qread(u);

        qread(v);

        add_edge(u,v);

        add_edge(v,u);

    }

    for(int i=1;i<=n;i++) deg[i]/=2;

    bfs();

    for(int i=1;i<=n;i++){

        if(deg[i]!=2) dfs2(i,0,0);

    }

    for(int i=1;i<=n;i++){

        ans=0;

        dfs3(i,0,0);

        qprint(ans);

        putchar('\n');

    }

}

巴特西

luogu P4183 Cow at Large P （暴力吊打点分治）(内有时间复杂度证明）

题面

分析

代码

最新文章

热门文章