Submission #3419094

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
const int    INF=(int)1e9;
const int    MOD=(int)1e9+7;
const double EPS=(double)1e-10;
struct Accelerate_Cin{
    Accelerate_Cin(){
        cin.tie(0); ios::sync_with_stdio(0);cout<<fixed<<setprecision(20);
    };
};

const int MAX_V = 100010;
vector<int> edge[MAX_V];
ll dp[MAX_V], dp2[MAX_V];
void dfs(int p, int x){
    vector<int> child;
    for(int t : edge[x]) if(t != p) child.push_back(t);
    for(int t : child) dfs(x, t);
    ll prod = 1;
    for(int t : child) prod = prod * dp[t] % MOD;
    dp2[x] = prod; prod = 1;
    for(int t : child) prod = prod * dp2[t] % MOD;
    dp[x] = (dp2[x] + prod) % MOD;
}
int main(){
    int n; cin >> n;
    for(int i=0;i<n-1;i++){
        int a, b; cin >> a >> b;
        a--; b--;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    dfs(-1, 0);
    cout << dp[0] << endl;
    return 0;
}

Submission Info

Judge Result