标签：22NOIP cnt int ll barrack edge low 军营 dp

include<bits/stdc++.h>

using namespace std;

using ll=long long;

const ll M = 1e9+7;

ll fast_pow(ll a,ll b){
ll res = 1;
while(b>0){
if(b&1)res=(resa)%M;;
a=(aa)%M;
b>>=1;
}
return res;
}

const int N = 6e5+5;

int n,m;
struct Edge{
int u,v;bool flag;
};
vector edges;
vector G[N];

int dfn[N],low[N],dfs_clock;

void tarjan(int u,int fa){
dfn[u]=low[u]=++dfs_clock;
for(int eid:G[u]){
int v = edges[eid].v;
if(!dfn[v]){
tarjan(v,u);
low[u]=min(low[u],low[v]);

        if(low[v]>low[u]){
            edges[eid].flag=1;
            edges[eid^1].flag=1;
        }
    }
    else if(v!=fa){
        low[u]=min(low[u],dfn[v]);
    }
}

}

int vertex_cnt[N],edge_cnt[N];
int fa[N];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int i,int j){
fa[find(i)]=find(j);
}
vector G2[N];

ll dp[N][2];
ll ans = 0;

ll subtree_edge[N];

void pre(int u,int father){
subtree_edge[u]=edge_cnt[u];
for(int v:G2[u]){
if(v==father)continue;
pre(v,u);
subtree_edge[u]+=subtree_edge[v]+1;
}
}

void dfs(int u,int fand){
bool flag=0;
for(int v:G2[u]){
if(v==fand)continue;
flag=1;
dfs(v,u);
}

// 是叶子节点
if(!flag){
    dp[u][0]=fast_pow(2,edge_cnt[u]);
    dp[u][1]=(fast_pow(2,vertex_cnt[u]))*(dp[u][0])%M;
}
else{
    if(u==fand)
        dp[u][0] = fast_pow(2,edge_cnt[u]+G2[u].size());
    else
        dp[u][0] = fast_pow(2,edge_cnt[u]+G2[u].size()-1);

    
    dp[u][1] = fast_pow(2,vertex_cnt[u]+edge_cnt[u]);
    for(int v:G2[u]){
        if(v==fand)continue;
        dp[u][0] = dp[u][0]*dp[v][0]%M;
        dp[u][1] = dp[u][1]*(2*dp[v][0]+dp[v][1])%M;
    }

}

dp[u][1] = (M+dp[u][1]-dp[u][0])%M;

ans = (ans + dp[u][1]*fast_pow(2,m-subtree_edge[u]-1)%M)%M;

}

int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
int u,v;
scanf("%d%d",&u,&v);
edges.push_back({u,v,0});
edges.push_back({v,u,0});
int cnt = edges.size();
G[u].push_back(cnt-2);
G[v].push_back(cnt-1);
}

// 因为图是连通的，只需要进行一次dfs
tarjan(1,1);

// 建立新图
for(int i=1;i<=n;i++){
    fa[i]=i;
}
for(auto e:edges){
    if(e.flag)continue;
    merge(e.u,e.v);
}
for(auto e:edges){
    int u=find(e.u),v=find(e.v);
    if(u==v){
        edge_cnt[u]++;
    }
    else{
        G2[u].push_back(v);
    }
}

for(int i=1;i<=n;i++){
    edge_cnt[i]/=2;
    vertex_cnt[find(i)]++;
}

pre(fa[1],fa[1]);
dfs(fa[1],fa[1]);    

printf("%lld\n",ans);

return 0;

}

标签：22NOIP,cnt,int,ll,barrack,edge,low,军营,dp
From： https://www.cnblogs.com/boyeyuan/p/17705584.html