cf 231 E. Cactus仙人掌图圆方树

题目链接： http://codeforces.com/problemset/problem/231/E

题意：

你现在有一个 $1e5$ 个点的仙人掌图（每个边最多只属于一个简单环），定义一条简单路径为一条边最多只被走过一次的路径。你现在有 $1e5$ 个询问，每次询问从 $a->b$ 有多少条简单路径，答案 $mod$ $1e9+7$。

做法：

如果你得到的是一棵树，那么很明显查询的结果一定是 $1$ 但是仙人掌图中的环会带来额外的答案，很容易得出如果从 $x$ 到 $y$ 经过了 $k$ 个环，那么答案就是 $2^{k}mod(1e9+7)$。

这里的经过不一定进入到环的内部，只是经过在环上的点也是算在答案中的（经过的时候绕环一圈也是符合简单路径的），这就带来了一些麻烦。

这个时候就想到了圆方树，我们先将整个图变成一棵树，在碰到入环的点的时候把这个值赋值为 $1$ ，然后用一次 $dfs$ 算出到每个点的距离，用 $dis[x]+dis[y]-2dis[lca=LCA(x,y)]$ 可以得到一个除了没加 $lca$ 以外的总值。

最后我们只要判断这个 $lca$ 是否在环上即可。

为什么呢，首先上面的加减是必要的。但是我们的 $lca$ 如果在环上， 那么这个环的影响会因为减去了两倍的 $dis[lca]$ 而消失，所以这个环我们还需要额外加上。

如果还不理解的话画个图感受一下就好啦。

代码

#include<bits/stdc++.h> #define rep(i,a,b) for(int i = (int)a;i<=(int)b;i++) using namespace std; typedef long long ll; typedef pair<ll,ll> pii; const int maxn=100005; const int maxm=300005; const ll mod=1e9+7; int low[maxn],dfn[maxn],dep[maxn],cou,is[maxn]; int n,m,q,fa[maxn][25],onC[maxn]; int S[maxn],top,dis[maxn],totp; ll twoq[maxn]; struct Graph{ int cnt,nex[maxm],to[maxm]; int head[maxn]; Graph(){memset(head,-1,sizeof(head)); cnt=0;} void add(int u,int v){ to[cnt]=v;nex[cnt]=head[u]; head[u]=cnt++; } }G,Cactu; void dfs(int u,int f){ for(int i=Cactu.head[u];~i;i=Cactu.nex[i]){ int v=Cactu.to[i]; if(v==f) continue; fa[v][0]=u,dep[v]=dep[u]+1,dis[v]=dis[u]+is[v]; dfs(v,u); } } void deal(int u,int v){ ++totp; is[u]=1; onC[u]=onC[v]=onC[totp]=1; while(1){ int p=S[top--]; Cactu.add(totp,p); onC[p]=1; if(p==v) break; } Cactu.add(u,totp); } void tarjan(int u,int f){ dfn[u]=low[u]=++cou; S[++top]=u; for(int i=G.head[u];~i;i=G.nex[i]){ int v=G.to[i]; if(v==f) continue; if(!dfn[v]){ tarjan(v,u); //这条边为非环边 直接建图 if(low[v]>dfn[u]) top--,Cactu.add(u,v); //如果u和v是恰好连接一个环的边 else if (low[v]==dfn[u]) deal(u,v); low[u]=min(low[u],low[v]); } //这条边连回更小的位置 else low[u]=min(low[u],dfn[v]); } } int LCA(int x,int y){ if(dep[x]<dep[y]) swap(x,y); for(int i=22;i>=0;i--) if(dep[x]-(1<<i)>=dep[y]) x=fa[x][i]; if(x==y) return x; for(int i=22;i>=0;i--) if(fa[x][i]!=fa[y][i]&&fa[x][i]!=-1){ x=fa[x][i],y=fa[y][i]; } return fa[x][0]; } int main(){ memset(fa,-1,sizeof(fa)); twoq[0]=1; for(int i=1;i<=100000;i++) twoq[i]=twoq[i-1]*2ll%mod; scanf("%d%d",&n,&m); totp=n; rep(i,1,m){ int x,y,z;scanf("%d%d",&x,&y); G.add(x,y); G.add(y,x); } tarjan(1,-1); dis[1]=is[1]; dfs(1,-1); for(int j=1;(1<<j)<=totp;j++){ for(int i=1;i<=totp;i++){ fa[i][j]=fa[fa[i][j-1]][j-1]; } } scanf("%d",&q); while(q--){ int u,v; scanf("%d%d",&u,&v); int lca=LCA(u,v); int ans=dis[u]+dis[v]-2*dis[lca]; if(onC[lca]) ans++; printf("%lld\n",twoq[ans]); } return 0; }