5305. 【NOIP2017提高A组模拟8.18】C (Standard IO)

Time Limits: 1000 ms Memory Limits: 131072 KB

Description

Input

Output

Sample Input

10 11

1 2

2 3

3 4

1 4

3 5

5 6

8 6

8 7

7 6

7 9

9 10

6

1 2

3 5

6 9

9 2

9 3

9 10

Sample Output

2

2

2

4

4

1

Data Constraint

Hint

题解

trajan裸题

加个树上RMQ

用lca优化一下就好了

代码

#include<cstdio>

#include<vector>

#define N 100010

#define mo 1000000007

#define ll long long

using namespace std;

vector<long>map[N],bian[N];

long low[N],dfn[N],tot,sta[N],w[N],cnt[N],top,num;

bool b[N],c[N],in[N];

void dfs(long now)

{   long i,to;

    low[now]=dfn[now]=++tot;

    b[now]=in[now]=true;

    sta[++top]=now;

    for(i=0;i<map[now].size();i++){

        to=map[now][i];

        if(!b[to]){

            c[bian[now][i]]=true;

            dfs(to);

            low[now]=min(low[now],low[to]);

        }

        else if(in[to]&&!c[bian[now][i]])

            low[now]=min(low[now],dfn[to]);

    }

    if(low[now]==dfn[now]){

        num++;

        to=0;

        while(now!=to){

            to=sta[top--];

            in[to]=false;

            w[to]=num;

            cnt[num]++;

        }

    }

}

void tarjan(long n)

{   long i;

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

        if(!b[i])

            dfs(i);

}

long sum[N][20],fa[N][20],dep[N];

void build(long now)

{   long i,to;

    b[now]=false;

    for(i=0;i<map[now].size();i++){

        to=map[now][i];

        if(b[to]){

            if(w[to]!=w[now]){

                if(cnt[w[now]]>1)

                    sum[w[to]][0]=1;

                fa[w[to]][0]=w[now];

                dep[w[to]]=dep[w[now]]+1;

            }

            build(to);

        }

    }

}

long lca(long x,long y)

{   long up;

    if(dep[x]>dep[y])

        swap(x,y);

    up=19;

    while(dep[y]>dep[x]){

        while(dep[y]-(1<<up)<dep[x]&&up>=0)

            up--;

        if(up<0)break;

        y=fa[y][up--];

    }

    up=19;

    while(x!=y){

        while(fa[x][up]==fa[y][up]&&up>=0)

            up--;

        if(up<0)break;

        x=fa[x][up];

        y=fa[y][up];

        up--;

    }

    if(x==y)

        return x;

    else

        return fa[x][0];

}

long suan(long x)

{   long up,ans=(cnt[x]>1)?1:0;

    up=19;

    while(dep[x]>0){

        while(dep[x]-(1<<up)<0&&up>=0)

            up--;

        if(up<0)break;

        ans=(ans+sum[x][up])%mo;

        x=fa[x][up];

    }

    return ans;

}

int main()

{   long n,m,i,j,x,y,q,ci,ans,l;

    scanf("%ld%ld",&n,&m);

    for(i=1;i<=m;i++){

        scanf("%ld%ld",&x,&y);

        map[x].push_back(y);

        map[y].push_back(x);

        bian[x].push_back(i);

        bian[y].push_back(i);

    }

    tarjan(n);

    build(1);

    n=num;

    for(j=1;(1<<j)<=n;j++)

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

            fa[i][j]=fa[fa[i][j-1]][j-1];

            sum[i][j]=(sum[fa[i][j-1]][j-1]+sum[i][j-1])%mo;

        }

    scanf("%ld",&q);

    for(i=1;i<=q;i++){

        scanf("%ld%ld",&x,&y);

        x=w[x];

        y=w[y];

        l=lca(x,y);

        ci=(((suan(x)+suan(y))%mo-2*suan(l)%mo)%mo+((cnt[l]>1)?1:0))%mo;

        ans=1;

        for(j=1;j<=ci;j++)

            ans=((ll)ans<<1)%mo;

        printf("%ld\n",ans);

    }

    return 0;

}

JZOJ 5305. 【NOIP2017提高A组模拟8.18】C (Standard IO)的相关教程结束。