제출 #1259519

#제출 시각아이디문제언어결과실행 시간메모리
1259519mohammad86Subtree (INOI20_subtree)C++20
100 / 100
42 ms16196 KiB
/* @Date    : 2025-08-16 18:17:55
   @Author  : hasan_86 */
#include <bits/stdc++.h>

using namespace std;

#define pb push_back

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int maxN = 1e5 + 100;
const int MOD = 1e9 + 7;

ll power(ll x, int p) {
    x %= MOD;
    ll res = 1;
    for (; p; p >>= 1) {
        if (p & 1) res = res * x % MOD;
        x = x * x % MOD;
    }
    return res;
}

vector<int> adj[maxN];

ll dp[maxN];
ll dp2[maxN];
ll mul[maxN];
int mark[maxN];
int par[maxN];

ll ans = 0;

void dfs(int x) {
    dp[x] = 1;
    mark[x] = 2;
    int spec = 0;
    for (int v : adj[x]) {
        if (mark[v] == 0) {
            par[v] = x;
            dfs(v);
            dp[x] = dp[x] * (dp[v] + 1) % MOD;
        } else if (mark[v] == 1) {
            spec = v;
        }
    }
    if (spec != 0) {
        int tmp = spec;
        mul[spec] = dp[spec];
        ll X = mul[spec];
        ll S = 0;
        ll Sp = 0;
        while (tmp != x) {
            S = (S + dp[tmp]) % MOD;
            Sp = (Sp + dp[tmp]) % MOD;
            mul[par[tmp]] = dp[par[tmp]] * power(dp[tmp] + 1, MOD - 2) % MOD;
            X = X * mul[par[tmp]] % MOD;
            tmp = par[tmp];
        }
        dp2[x] = (dp[x] - X + MOD) % MOD;
        S = (S + dp2[x]) % MOD;
        dp2[spec] = dp2[x] * mul[spec];
        int v = spec;
        while (v != x) {
            dp2[v] = (dp2[v] - X + MOD) % MOD;
            S = (S + dp2[v]) % MOD;
            if (par[v] != x)
                dp2[par[v]] = dp2[v] * mul[par[v]] % MOD;
            v = par[v];
        }
        dp[x] = (S - Sp + MOD) % MOD;
    }
    mark[x] = 1;
    ans = (ans + dp[x]) % MOD;
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].pb(v);
        adj[v].pb(u);
    }

    dfs(1);

    cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...