Submission #1259519

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259519		mohammad86	Subtree (INOI20_subtree)	C++20	100 / 100	42 ms	16196 KiB

Main

/* @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;
}

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