Submission #1003162

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003162		vjudge1	Subtree (INOI20_subtree)	C++17	12 / 100	469 ms	1048576 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define oo 1e9

const int MAX = 1e5 + 5, MOD = 1e9 + 7;
int n, m;
vector<int> g[MAX];
int dp[MAX];

void dfs(int node, int p){
    dp[node] = 1;
    for(int to : g[node]){
        if(to == p) continue;
        dfs(to, node);
        dp[node] = dp[node] * (dp[to] + 1) % MOD;
    }
}

void solve(){
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 1);
    int ans = 0;
    for(int i = 1; i <= n; i++){
        ans = (ans + dp[i]) % MOD;
    }
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    while(t--){
        solve();
    }
}

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