Codeforces 231E - Cactus
題意:与えられたn(2<=n<=10000000)個の点の無方向図であり、1つの点は最大1つのsimple cycleにのみ存在し、simple pathをu->vと定義する経路が異なる、すなわち異なる.
k(1<=k<=10000000)グループはuvを尋ね,u->vのsimpleパスの個数を問う.
标题:縮点+増倍lca
Sureオリジナル、転載は出典を明記してください
k(1<=k<=10000000)グループはuvを尋ね,u->vのsimpleパスの個数を問う.
标题:縮点+増倍lca
Sureオリジナル、転載は出典を明記してください
#include <iostream>
#include <cstdio>
#include <memory.h>
#define MIN(a , b) ((a) < (b) ? (a) : (b))
using namespace std;
const int mod = 1000000007;
const int maxn = 100002;
const int fix = 16;
struct node
{
int v;
int next;
}edge[maxn << 1];
int head[maxn],dfn[maxn],low[maxn],belong[maxn],cnt[maxn],cycle[maxn];
int s[maxn],dis[maxn],dep[maxn],fa[maxn][fix],U[maxn],V[maxn];
bool vis[maxn],instack[maxn];
int m,n,q,idx,tmpdfn,tot,top;
void swap(int &a,int &b)
{
int tmp = a;
a = b;
b = tmp;
return;
}
void init()
{
memset(head,-1,sizeof(head));
memset(cnt,0,sizeof(cnt));
memset(fa,0,sizeof(fa));
memset(dis,0,sizeof(dis));
memset(cycle,0,sizeof(cycle));
memset(vis,false,sizeof(vis));
memset(instack,false,sizeof(instack));
idx = tmpdfn = tot = 0;
return;
}
void addedge(int u,int v)
{
edge[idx].v = v;
edge[idx].next = head[u];
head[u] = idx++;
edge[idx].v = u;
edge[idx].next = head[v];
head[v] = idx++;
return;
}
void read()
{
for(int i=0;i<m;i++)
{
scanf("%d %d",&U[i],&V[i]);
addedge(U[i],V[i]);
}
return;
}
void tarjan(int st,int pre)
{
dfn[st] = low[st] = tmpdfn++;
vis[st] = instack[st] = true;
s[top++] = st;
for(int i=head[st];i != -1;i=edge[i].next)
{
if(edge[i].v == pre) continue;
if(vis[edge[i].v] == false)
{
tarjan(edge[i].v , st);
low[st] = MIN(low[st] , low[edge[i].v]);
}
else if(instack[edge[i].v])
{
low[st] = MIN(low[st] , dfn[edge[i].v]);
}
}
if(low[st] == dfn[st])
{
int u;
tot++;
do
{
u = s[--top];
instack[u] = false;
belong[u] = tot;
cnt[tot]++;
}while(u != st);
if(cnt[tot] > 1) cycle[tot] = 1;
}
return;
}
void make()
{
for(int i=1;i<=n;i++)
{
if(vis[i] == false)
{
top = 0;
tarjan(i , -1);
}
}
memset(head,-1,sizeof(head));
idx = 0;
for(int i=0;i<m;i++)
{
int u = belong[U[i]];
int v = belong[V[i]];
if(u != v) addedge(u , v);
}
return;
}
void dfs(int st,int pre,int d)
{
dep[st] = d;
for(int i=head[st];i != -1;i=edge[i].next)
{
if(edge[i].v == pre) continue;
fa[edge[i].v][0] = st;
for(int j=1;j<fix;j++)
{
fa[edge[i].v][j] = fa[fa[edge[i].v][j-1]][j-1];
}
dis[edge[i].v] = dis[st] + cycle[edge[i].v];
dfs(edge[i].v , st , d + 1);
}
return;
}
int lca(int u,int v)
{
if(dep[u] > dep[v]) swap(u , v);
if(dep[u] < dep[v])
{
int del = dep[v] - dep[u];
for(int i=0;i<fix;i++)
{
if(del & (1 << i))
{
v = fa[v][i];
}
}
}
if(u != v)
{
for(int i=fix-1;i>=0;i--)
{
if(fa[u][i] != fa[v][i])
{
u = fa[u][i];
v = fa[v][i];
}
}
u = fa[u][0];
v = fa[v][0];
}
return u;
}
int quick_pow(int x)
{
__int64 res = 1LL,tmp = 2 * 1LL;
while(x)
{
if(x & 1)
{
res *= tmp;
res %= mod;
}
tmp *= tmp;
tmp %= mod;
x >>= 1;
}
return (int)res;
}
void solve()
{
dis[belong[1]] = cycle[belong[1]];
dfs(belong[1] , -1 , 0);
scanf("%d",&q);
int u,v;
while(q--)
{
scanf("%d %d",&u,&v);
u = belong[u];
v = belong[v];
int l = lca(u , v);
int c = dis[u] + dis[v] - 2 * dis[l] + cycle[l];
printf("%d
",quick_pow(c));
}
return;
}
int main()
{
while(~scanf("%d %d",&n,&m))
{
init();
read();
make();
solve();
}
return 0;
}