Cactus CodeForces - 231E (无向图缩环)

大意: 给定无向图, 每个点最多属于一个简单环, 多组询问, 求给定起点终点, 有多少条简单路径.

先缩环, 然后假设两点树上路径经过$cnt$个环, 那么答案就为$2^{cnt}$.

要注意缩环建树时要加单向边.

#include <iostream>

#include <algorithm>

#include <cstdio>

#include <queue>

#define REP(i,a,n) for(int i=a;i<=n;++i)

#define pb push_back

using namespace std;

template <class T> void rd(T &x){x=0;bool f=0;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=1;c=getchar();}while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();}if(f)x=-x;}

const int N = 1e6+10, P = 1e9+7;

int n,m,dep[N],fa[N];

int s[N],vis[N],sz[N];

int son[N],top[N],v[N],fac[N];

vector<int> g[N],gg[N];

int Find(int x) {return s[x]?s[x]=Find(s[x]):x;}

void add(int x, int y) {

	x=Find(x),y=Find(y);

	if (x!=y) s[x]=y;

}

void get(int x, int y) {

    if (dep[x]<dep[y]) return;

	vis[y] = 1;

    for (; x!=y; x=fa[x]) add(x,y),vis[x]=1;

}

void dfs(int x, int f) {

    fa[x]=f,dep[x]=dep[f]+1;

    for (int y:g[x]) if (y!=f) {

        if (dep[y]) get(x,y);

        else dfs(y,x);

    }

}

void dfs2(int x, int f, int d) {

	sz[x]=1,fa[x]=f,dep[x]=d,v[x]=v[f]+vis[x];

	for (int y:gg[x]) if (y!=f) {

		dfs2(y,x,d+1),sz[x]+=sz[y];

		if (sz[y]>sz[son[x]]) son[x]=y;

	}

}

void dfs3(int x, int tf) {

	top[x] = tf;

	if (son[x]) dfs3(son[x],tf);

	for (int y:gg[x]) if (!top[y]) dfs3(y,y);

}

int lca(int x, int y) {

	while (top[x]!=top[y]) {

		if (dep[top[x]]<dep[top[y]]) swap(x,y);

		x = fa[top[x]];

	}

	return dep[x]<dep[y]?x:y;

}

int main() {

	fac[0]=1;

	REP(i,1,N-1) fac[i]=fac[i-1]*2%P;

	rd(n),rd(m);

	REP(i,1,m) {

		int u, v;

		rd(u),rd(v);

		if (u==v) continue;

		g[u].pb(v),g[v].pb(u);

	}

	dfs(1,0);

	int rt = 1;

	REP(i,1,n) if (vis[i]) rt = Find(i);

	REP(i,1,n) {

		for (int j:g[i]) {

			int u=Find(i),v=Find(j);

			if (u!=v) gg[u].pb(v);

		}

	}

	dfs2(rt,0,0),dfs3(rt,rt);

	scanf("%d", &m);

	while (m--) {

		int x, y;

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

		x = Find(x), y = Find(y);

		int l = lca(x,y);

		printf("%d\n", fac[v[x]+v[y]-v[l]-v[fa[l]]]);

	}

}