样例全过,但是寄成0分,悬关求条
查看原帖
样例全过,但是寄成0分,悬关求条
529247
BLX32M_10楼主2024/8/17 09:31
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 5e5 + 5, maxm = 1e6 + 5, mod = 1e9 + 7;
int n, m, dfn[maxm], low[maxm], dcnt, dc[maxm], bd[maxm], ec;
bool vis[maxm];
int sz;
vector <int> ed[maxn], eg[maxn], dcc[maxm];
unordered_set <int> gb[maxn];
stack <int> st;
inline void tarjan(int u, int fa)
{
    low[u] = dfn[u] = ++dcnt, vis[u] = 1;
    st.push(u);
    bool flag = 0;
    for (int v : ed[u])
    {
        if (!dfn[v])
        {
            tarjan(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] > low[u])
            {
                gb[u].insert(v);
                gb[v].insert(u);
            }
        }
        else if (v != fa || flag)
            low[u] = min(low[u], dfn[v]);
        else
            flag = 1;
    }
    if (dfn[u] == low[u])
    {
        sz++;
        vector <int> vec;
        vec.push_back(u);
        bd[u] = sz;
        dc[u] = u;
        while (st.top() != u)
        {
            bd[st.top()] = sz;
            dc[st.top()] = u;
            vec.push_back(st.top());
            st.pop();
        }
        st.pop();
        dcc[sz] = vec;
    }
}
inline void dfs(int u)
{
    vis[u] = 1;
    for (int v : ed[u])
    {
        if (dc[u] != dc[v])
        {
            ec++;
            eg[dc[u]].push_back(dc[v]);
            eg[dc[v]].push_back(dc[u]);
        }
        else if (!vis[v])
            dfs(v);
    }
}
int f[maxn], cnt[maxn], m2[maxm], res;
inline int dp(int u, int fa)
{
    f[u] = m2[dcc[bd[u]].size()];
    for (int v : eg[u])
    {
        if (v == fa)
            continue;
        dp(v, u);
        cnt[u] += cnt[v] + 1;
        f[u] = (f[u] * (m2[cnt[v] + 1] + f[v]) % mod) % mod;
    }
    f[u] = (f[u] - m2[cnt[u]] + mod) % mod;
    int x = f[u];
    for (int v : eg[u])
    {
        if (v == fa)
            continue;
        x = (x - f[v] * m2[cnt[u] - cnt[v] - 1] % mod + mod) % mod;
    }
    x = x * m2[ec - cnt[u]] % mod;
    res = (res + x) % mod;
}
signed main()
{
    freopen("barrack3.in", "r", stdin);
    m2[0] = 1;
    for (int i = 1; i <= maxm - 3; i++)
    {
        m2[i] = (m2[i - 1] << 1) % mod;
    }
    scanf("%lld %lld", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%lld %lld", &u, &v);
        ed[u].push_back(v);
        ed[v].push_back(u);
    }
    tarjan(1, 0);
    dfs(1);
    dp(1, 0);
    printf("%lld", res * m2[m - ec] % mod);
    return 0;
}
2024/8/17 09:31
加载中...