萌新求调Tarjan缩点树形DP 0pts万紫千红

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int mod = 1e9+7;
int MM(const int x,const int MOD = mod){return x%MOD;}
const int N = 5e5+5;
const int M = 1e6+5;

int n,m;

struct edge{
    int nxt,to;
} g[M<<1],tree[M<<1];

int head[M<<1],ht[M<<1],ec,ect;

void add(int u,int v){
    g[++ec].nxt=head[u];
    g[ec].to=v;
    head[u]=ec;
}

void addtree(int u,int v){
    tree[++ect].nxt=ht[u];
    tree[ect].to=v;
    ht[u]=ect;
}

int low[N],dfn[N],cnt,vis[N],ccnt,belong[N],csiz[N],s[N],e[N];
stack<int> sta;

void tarjan(int u,int fa){
    dfn[u]=low[u]=(++cnt);
    vis[u]=1;sta.push(u);
    for(int i=head[u];i;i=g[i].nxt){
        int v=g[i].to;
        if(v==fa) continue;
        if(!dfn[v]){
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(dfn[u]==low[u]){
        ccnt++;
        int v;
        do{
            v=sta.top();sta.pop();
            belong[v]=ccnt;csiz[ccnt]++;
        }while(u!=v);
    }
}

int pow(int a,int b,const int mod){
    if(b==0) return 1;
    if(b==1) return MM(a,mod);
    int ret=pow(a,b>>1,mod);
    ret=MM(ret*ret, mod);
    if(b&1) ret=MM(ret*a,mod);
    return ret;
}

void dfs(int u,int fa){
    s[u]=e[u];
    for(int i=ht[u];i;i=tree[u].nxt){
        int v=tree[u].to;
        if(v==fa) continue;
        dfs(v,u);
        s[u]+=(s[v]+1);
    }
}

int f[N][2],ans;

void dp(int u,int fa){
    for (int i=ht[u],v;i;i=tree[i].nxt) {
        v = tree[i].to;
        if (v==fa) continue;
        dp(v,u);
        f[u][1] =MM(f[u][1] * MM(MM(MM(f[v][0]<<1)+f[v][1]))+MM(f[u][0]*f[v][1]));
        f[u][0] = MM(f[u][0]*MM(MM(f[v][0]<<1)));
    }
    if(u==1) ans=MM(ans+f[u][1]);
    else ans=MM(ans+MM(f[u][1]*pow(2,s[1]-s[u]-1,mod)));
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        add(u,v);add(v,u);
    }
    tarjan(1,0);
    for(int i=1;i<=n;i++){
        for(int u=head[i];u;u=g[u].nxt){
            int j=g[u].to;
            if(belong[i]==belong[j]) e[belong[i]]++;
            else addtree(belong[i],belong[j]);
        }
    }
    for(int i=1;i<=ccnt;i++){
        e[i]>>=1;
        f[i][0]=pow(2,e[i],mod);
        f[i][1]=pow(2,csiz[i]+e[i])-f[i][0];
    }
    dfs(1,0);
    dp(1,0);
    cout<<ans;
    return 0;
}