Submission #1330104

#TimeUsernameProblemLanguageResultExecution timeMemory
1330104edoSubtree (INOI20_subtree)C++20
100 / 100
53 ms25088 KiB
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int md = 1e9 + 7;

void add(int &a, int b) {
    a += b;
    if(a >= md) a -= md;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    for(int i = 0, u, v; i < m; i++) {
        cin >> u >> v;
        g[--u].push_back(--v);
        g[v].push_back(u);
    }
    
    vector<int> dp(n), mark(n), par(n), low(n, 1e9), d(n), go(n, -1), dp1(n), pref(n);
    auto dfs = [&](auto&& self, int u, int p = -1) -> void {
        par[u] = p;
        mark[u] = 1;
        // low[u] = d[u];
        for(int v : g[u]) {
            if(mark[v] == 0) {
                d[v] = d[u] + 1;
                self(self, v, u);
                if(low[v] <= d[u]) {
                    go[u] = v;
                }
                low[u] = min(low[u], low[v]);
            }
            else if(v != p && mark[v] == 1) {
                low[u] = d[v];
            }
        }
        mark[u] = 2;
    };

    auto  dfs1 = [&](auto&& self, int u) -> void {
        mark[u] = 0;
        for(int v : g[u]) {
            if(mark[v] == 2) self(self, v);
        }
        if(low[u] == d[u]) {
            vector<int> c;
            for(int v = u; ~v; v = go[v]) {
                c.push_back(v);
            }
            int prod = 1, sum = 0;
            for(int v : c) {
                dp1[v] = 1;
                for(int x : g[v]) {
                    if(par[x] == v && x != go[v]) {
                        dp1[v] = (1LL * dp1[v] * (dp[x] + 1)) % md;
                    }
                }
                prod = (1LL * prod * dp1[v]) % md;
                add(sum, prod);
                pref[v] = sum;
            }

            prod = 1;
            for(int i = c.size(); --i;) {
                int v = c[i];
                dp[u] = (dp[u] + 1LL * pref[par[v]] * prod) % md;
                prod = (1LL * prod * dp1[v]) % md;
            }
        }
        else {
            dp[u] = 1;
            for(int v : g[u]) {
                if(par[v] == u) 
                    dp[u] = (1LL * dp[u] * (dp[v] + 1)) % md;
            }
        }
    };
    dfs(dfs, 0);
    dfs1(dfs1, 0);

    int ans = 0;
    for(auto &i : dp) 
        add(ans, i);
    cout << ans;

    return 0;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...