简要题意
给定一个 \(n\) 个点，\(m\) 条边的无向图。你可以选择若干个点和边，满足去掉一条原图中除”被选择的边“的边后，被选择的点仍然两两可达。询问选择点和边的方案数。
分析
首先，这是连通性相关问题，考虑 Tarjan。注意到缩点不影响连通性，因此在缩点后把图转化为一棵树。
现在我们约定：
-
一号节点是树根；
-
\(sz_u\) 表示 \(u\) 子树内的边的数量；
-
\(ct_u\) 表示 \(u\) 点表示在原图中表示多少个点；
-
\(M\) 表示树的总边数，即 \(M=sz_1\)。
因为非树边选不选无所谓，因此我们只讨论树边，最后答案乘上 \(2^{m-M}\) 即可。
显然，选择的点之间的路径上的边是一定要选的，因此我们考虑设计 \(f_u\) 为 \(u\) 子树内选了至少一点，且和 \(u\) 之间的边都选择了的方案数。
那么我们对 \(u\) 的一个儿子 \(v\) 进行分类讨论：
-
若 \(v\) 的子树内有点被选：那么 \((u,v)\) 必选，贡献为 \(f_v\)；
-
若 \(v\) 的子树内没有点被选：整个 \(v\) 子树内的边和 \((u,v)\) 选不选都行，贡献为 \(2^{sz_v+1}\)。
然后在满足上述情况的前提下，\(u\) 内的点选不选都可以，于是上述贡献还需要乘上 \(2^{ct_u}\)。
但是这样 \(u\) 子树内没有选点的情况也被统计到了，因此我们要减去 \(2^{sz_u}\)。
综上，转移为：
接下来是统计答案，因为每一种方案只能被统计一次，因此想到在所有点的 LCA 处进行统计。
但是 \(f_u\) 中不仅包含了 \(u\) 为 LCA 的方案，还包含了 \(u\) 不为 LCA 的方案（废话）。然后我们发现 \(u\) 不为 LCA 时，被选的点都在一个儿子 \(v\) 的子树内。那么这时 \(v\) 子树内的方案数为 \(f_v\)，\(u\) 子树内除 \(v\) 子树内的边对方案数的贡献为 \(2^{sz_u-sz_v-1}\)（ \((u,v)\) 必选，所以要减一），同时 \(u\) 子树外的边可选可不选，因此还要在容斥完后乘上 \(2^{M-sz_u}\)。
总而言之，就是：
代码
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define Inf (1ll<<60)
#define For(i,s,t) for(int i=s;i<=t;++i)
#define Down(i,s,t) for(int i=s;i>=t;--i)
#define ls (i<<1)
#define rs (i<<1|1)
#define bmod(x) ((x)>=p?(x)-p:(x))
#define lowbit(x) ((x)&(-(x)))
#define End {printf("NO\n");exit(0);}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
inline void ckmx(int &x,int y){x=(x>y)?x:y;}
inline void ckmn(int &x,int y){x=(x<y)?x:y;}
inline void ckmx(ll &x,ll y){x=(x>y)?x:y;}
inline void ckmn(ll &x,ll y){x=(x<y)?x:y;}
inline int min(int x,int y){return x<y?x:y;}
inline int max(int x,int y){return x>y?x:y;}
inline ll min(ll x,ll y){return x<y?x:y;}
inline ll max(ll x,ll y){return x>y?x:y;}
char buf[1<<20],*p1,*p2;
#define gc() (p1 == p2 ? (p2 = buf + fread(p1 = buf, 1, 1 << 20, stdin), p1 == p2 ? EOF : *p1++) : *p1++)
#define read() ({\int x = 0, f = 1;\char c = gc();\while(c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = gc();\while(c >= '0' && c <= '9') x = x * 10 + (c & 15), c = gc();\f * x;\
})
void write(int x){if(x>=10) write(x/10);putchar(x%10+'0');
}
const int N=5e5+100,p=1e9+7,M=1e6+500;
int n,m;
struct Edge{int from,f,to;}e[M<<1];
int num,h[N];
void add(int f,int t){e[++num].from=h[f],e[num].f=f,e[num].to=t,h[f]=num;}
int dfn[N],low[N],col[N],sz[N],dfu,cnt,pw[M],s[N],tail;
bool in[N];
void tarjan(int u,int fa){dfn[u]=low[u]=++dfu;in[u]=true;s[++tail]=u;for(int i=h[u];i;i=e[i].from){int v=e[i].to;if(v==fa) continue;if(!dfn[v]){tarjan(v,u);low[u]=min(low[u],low[v]);}else if(in[v])low[u]=min(low[u],dfn[v]);}if(low[u]==dfn[u]){++cnt;while(tail){int v=s[tail];--tail;in[v]=false;col[v]=cnt;++sz[cnt];if(v==u) break;}}
}
int fa[N];
int find(int x){return fa[x]=(fa[x]==x ? x :find(fa[x]));}
void build(){int old=num;num=0;For(i,1,n) h[i]=0,fa[i]=i;for(int i=1;i<=old;i+=2){int u=col[e[i].f],v=col[e[i].to];if(find(u)==find(v)) continue;fa[find(u)]=find(v);add(u,v);add(v,u);}
}
int f[N],ct[N],ans;
void dfs(int u,int fa){f[u]=1;for(int i=h[u];i;i=e[i].from){int v=e[i].to;if(v==fa) continue;dfs(v,u);ct[u]+=ct[v]+1;f[u]=1ll*f[u]*bmod(pw[ct[v]+1]+f[v])%p;}f[u]=1ll*f[u]*pw[sz[u]]%p;f[u]=bmod(f[u]+p-pw[ct[u]]);int res=0;for(int i=h[u];i;i=e[i].from){int v=e[i].to;if(v==fa) continue;res=bmod(res-1ll*f[v]*pw[ct[u]-ct[v]-1]%p+p);}res=bmod(res+f[u]);ans=bmod(ans+1ll*res*pw[cnt-ct[u]-1]%p);
}
int main()
{
#if !ONLINE_JUDGEfreopen("test.in","r",stdin);freopen("test.out","w",stdout);
#endif n=read(),m=read();int u,v;For(i,1,m) u=read(),v=read(),add(u,v),add(v,u);tarjan(1,0);build();pw[0]=1;For(i,1,m+100) pw[i]=2ll*pw[i-1]%p;dfs(1,0);//For(i,1,cnt) printf("%d %d\n",f[i],ct[i]);printf("%d",1ll*ans*pw[m-cnt+1]%p);return 0;
}