Submission #1122198

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122198		Hamed_Ghaffari	Subtree (INOI20_subtree)	C++17	100 / 100	66 ms	26956 KiB

Main

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

using ll = long long;

#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)
#define pb push_back
#define all(x) x.begin(), x.end()
#define SZ(x) int(x.size())

const int MXN = 1e5+5, MOD = 1e9+7;

int n, m;
vector<int> g[MXN];
int h[MXN], par[MXN];
bool mark[MXN];
ll dp[MXN];

void dfs(int v) {
    int BE=0;
    dp[v] = 1;
    for(int u : g[v])
        if(!h[u]) {
            h[u] = h[v]+1; 
            par[u] = v;
            dfs(u);
            (dp[v] *= dp[u]+1) %= MOD;
        }
        else if(h[u]>h[v]) BE = u;
    if(BE) {
        int u = BE;
        ll bad=1;
        vector<int> vec;
        while(1) {
            vec.pb(u);
            mark[u] = 1;
            for(int w : g[u])
                if(!mark[w] && h[w]>h[u]) 
                    (bad *= dp[w]+1) %= MOD;
            if(u == v) break;
            u = par[u];
        }
        (dp[v] += MOD-bad) %= MOD;
        reverse(all(vec));
        vector<ll> sum;
        ll cur = 1;
        for(int w : g[v])
            if(!mark[w] && h[w]>h[v])
                (cur *= dp[w]+1) %= MOD;
        sum.pb(cur);
        for(int i=1; i<SZ(vec); i++) {
            for(int w : g[vec[i]])
                if(!mark[w] && h[w]>h[vec[i]])
                    (cur *= dp[w]+1) %= MOD;
            sum.pb((sum.back()+cur)%MOD);
        }
        ll down=1;
        for(int i=SZ(vec)-1; i>=2; i--) {
            for(int w : g[vec[i]])
                if(!mark[w] && h[w]>h[vec[i]])
                    (down *= dp[w]+1) %= MOD;
            (dp[v] += down*sum[i-2]) %= MOD;
        }
        for(int w : vec) mark[w] = 0;
    }
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1, u,v; i<=m; i++) {
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    h[1] = 1;
    dfs(1);
    ll ans=0;
    for(int i=1; i<=n; i++) (ans += dp[i]) %= MOD;
    cout << ans << '\n';
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 30 / 30
• Subtask 4: 50 / 50