正题
题目链接:https://www.luogu.com.cn/problem/P8867
题目大意
给出一个 \(n\) 个点 \(m\) 条边的无向联通图。
标记至少一个点，标记一些边，要求删除任何一条标记边外的边后，标记的点仍然联通。
求方案数对 \(10^9+7\) 取模
\(1\leq n\leq 5\times 10^5,n-1\leq m\leq 10^6\)
解题思路
显然非桥随便标记，所以先把边双缩起来成一棵树。
然后考虑树形 \(dp\) ，考虑以 \(1\) 为根，然后对于每个根可以求出所有标记边的 \(LCA\) 为这个点的方案数。
设 \(f_{i,0/1/2}\) 表示 \(i\) 的子树中没有标记点，\(i\) 子树中有标记点，但 \(LCA\) 不为/为 \(i\)
然后 \(dp\) 就好了，时间复杂度：\(O(n)\)
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cctype>
#include<vector>
#include<stack>
#define ll long long
using namespace std;
const ll N=5e5+10,P=1e9+7;
ll n,m,dfc,cnt,ans;
ll f[N][3],siz[N],pw[N<<1],num[N];
ll dfn[N],low[N],col[N];
vector<ll> G[N],T[N];
bool ins[N];stack<ll> s;
ll read(){
ll x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
void tarjan(ll x,ll fa){
dfn[x]=low[x]=++dfc;
s.push(x);ins[x]=1;
for(ll i=0;i<G[x].size();i++){
ll y=G[x][i];
if(y==fa)continue;
if(!dfn[y]){
tarjan(y,x);
low[x]=min(low[x],low[y]);
}
else if(ins[x])
low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
ll k;cnt++;
do{
k=s.top();s.pop();
col[k]=cnt;ins[k]=0;
}while(k!=x);
}
return;
}
void dp(ll x,ll fa){
siz[x]=1;f[x][0]=1;f[x][2]=pw[num[x]]-1;
for(ll i=0;i<T[x].size();i++){
ll y=T[x][i];
if(y==fa)continue;dp(y,x);siz[x]+=siz[y];
f[x][2]=((f[y][1]+f[y][2])%P*f[x][1]%P+(f[y][0]*2+f[y][1]+f[y][2])%P*f[x][2]%P)%P;
f[x][1]=(f[x][0]*(f[y][1]+f[y][2])%P+f[x][1]*f[y][0]%P*2ll%P)%P;
f[x][0]=f[x][0]*f[y][0]%P*2ll%P;
}
(ans+=f[x][2]*pw[cnt-siz[x]]%P)%=P;
return;
}
signed main()
{
// freopen("barrack.in","r",stdin);
// freopen("barrack.out","w",stdout);
n=read();m=read();pw[0]=1;
for(ll i=1;i<=1e6;i++)pw[i]=pw[i-1]*2ll%P;
for(ll i=1;i<=m;i++){
ll x=read(),y=read();
G[x].push_back(y);
G[y].push_back(x);
}
tarjan(1,0);
for(ll x=1;x<=n;x++){
for(ll i=0;i<G[x].size();i++)
if(col[G[x][i]]!=col[x])
T[col[x]].push_back(col[G[x][i]]);
num[col[x]]++;
}
dp(1,0);ans=(ans+P)%P;
printf("%lld\n",ans*pw[m-cnt+1]%P);
return 0;
}